#include<bits/stdc++.h> #define int long long using namespace std; int dp[1005][1005],w[1005],c[1005]; signed 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 = 0;j <= m;j++){ dp[i][j] = dp[i - 1][j]; if (j >= w[i]){ dp[i][j] = max(dp[i][j],dp[i - 1][j - w[i]] + c[i]); } } } cout<<dp[n][m]; return 0; }