#include<bits/stdc++.h> #pragma GCC optimize(3) #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; const int N=310; const int INF=0x3f3f3f3f; int dp[N][N],n,m,w[N],c[N]; int main() { IOS; cin>>m>>n; for(int i=1;i<=n;++i) { cin>>w[i]>>c[i]; } for(int i=1;i<=n;++i) { for(int v=m;v>0;--v) { if(v>=w[i]) dp[i][v]=max(dp[i-1][v],(dp[i-1][v-w[i]]+c[i])); else dp[i][v]=dp[i-1][v]; } } cout<<dp[n][m]; return 0; }