#include<bits/stdc++.h> using namespace std; int n,m,v[1001],w[1001],ans,dp[1001][1001]; void dfs(int i,int wi,int vi){ if(i>n){ if(vi>ans)ans=vi; return ; } if(wi+w[i]<=m and dp[i][wi+w[i]]<vi+v[i]){ dp[i][wi+w[i]]=vi+v[i]; dfs(i+1,wi+w[i],vi+v[i]); } if(dp[i][wi]<vi){ dp[i][wi]=vi; dfs(i+1,wi,vi); } dfs(i+1,wi,vi); } int main() { cin>>m>>n; memset(dp,-1,sizeof(dp)); for(int i=1;i<=n;i++){ cin>>w[i]>>v[i]; } ans=0; dfs(1,0,0); cout<<ans<<endl; }