#include<bits/stdc++.h> using namespace std; int t,n,dp[105][1005],t1[105],v[105]; int main() { int t,n; cin>>t>>n; for (int i=1;i<=n;i++){ cin>>t1[i]>>v[i]; } for (int i=1;i<=n;i++){ for (int j=1;j<=t;j++){ if(j<t1[i]){ dp[i][j]=dp[i-1][j]; }else{ dp[i][j]=max(dp[i-1][j],dp[i-1][j-t1[i]]+v[i]); } } } cout<<dp[n][t]; return 0; }