#include<iostream> using namespace std; long long dp[1001][10001],w[1001],c[1001]; int main(){ long long n,m; cin>>m>>n; for(int i=1;i<=n;i++){ cin>>w[i]>>c[i]; } for(int i=1;i<=n;i++){ //i为i个物品 for(int j=1;j<=m;j++){ //j为背包总容量 if(j<w[i]){ dp[i][j]=dp[i-1][j]; } if(j>=w[i]){ dp[i][j]=max(dp[i-1][j],c[i]+dp[i-1][j-w[i]]); } } } cout<<dp[n][m]<<endl; return 0; }