#include<iostream> using namespace std; int w[31],c[31]; int dp[31][201]; int main(){ int n,m; cin>>m>>n; for(int i=1;i<=n;i++){ cin>>w[i]>>c[i]; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(j<w[i]){ dp[i][j]=dp[i-1][j]; } else if(dp[i-1][j]>dp[i][j-w[i]]+c[i]){ dp[i][j]=dp[i-1][j]; } else dp[i][j]=dp[i][j-w[i]]+c[i]; } } cout<<"max="<<dp[n][m]<<endl; return 0; }