#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 && 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; for (int i=1;i<=n;i++) cin>>w[i]>>v[i]; ans=0; dfs(1,0,0); cout<<ans<<endl; return 0; }