#include<iostream> using namespace std; int dp[1001][1001],w[1001],c[1001]; int main(){ int m,n; 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=1;j<=m;j++){ if(j-w[i]>=0){ dp[i][j]=max(dp[i-1][j-w[i]]+c[i],dp[i-1][j]); } else dp[i][j]=dp[i-1][j]; } } cout<<dp[n][m]<<endl; return 0; }