#include<iostream> #include<cstring> #include<algorithm> using namespace std; int w[11000],c[11000],dp[11000][11000]; int main(){ ios::sync_with_stdio(false); cin.tie(0); memset(w,0,sizeof(w)); memset(c,0,sizeof(c)); memset(dp,0,sizeof(dp)); int m,t; cin>>t>>m; for(int i = 1; i <= m; i++){ cin>>w[i]>>c[i]; } for(int i = 1; i <= m; i++){ for(int j = 1;j <= t; j++){ if(j >= w[i]){ dp[i][j] = max(dp[i-1][j-w[i]]+c[i],dp[i-1][j]); }else{ dp[i][j] = dp[i-1][j]; } } } cout<<dp[m][t]; return 0; }