#include<iostream> #include<algorithm> using namespace std; int w[10100],c[10100],dp[10100][10100]; int main(){ ios::sync_with_stdio(false); cin.tie(0); 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][i] = dp[i-1][j]; } } } cout<<dp[m][t]; return 0; }