#include<bits/stdc++.h>

using namespace std;

int n,m,w[35],c[35];

int dp[200];

signed main(){

cin>>n>>m;

for(int i=1;i<=m;i++)

{

cin>>w[i]>>c[i];

}

for(int i=1;i<=m;i++)

{

for(int j=w[i];j<=n;j++){

	dp[j]=max(dp[j],dp[j-w[i]]+c[i]);


}//cout<<endl;

}

cout<<"max="<<dp[n];

}