#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];

}

#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]; }