#include<bits/stdc++.h> using namespace std; long long m,n,ans=0; struct st { long long c,w; }f[1097]; long long dp[1097][1097]; void dfs(int i,int wi,int ci) { if(i>n) { if(ci>ans)ans=ci; return; } if(wi+f[i].w<=m&&dp[i][wi+f[i].w]<ci+f[i].c) { dp[i][wi+f[i].w]=ci+f[i].c; dfs(i+1,f[i].w+wi,f[i].c+ci); } if(dp[i][wi]<ci) { dp[i][f[i].w]=ci; dfs(i+1,wi,ci); } } int main() { cin>>m>>n; memset(dp,-1,sizeof dp); for(int i=1;i<=n;i++) { cin>>f[i].w>>f[i].c; } dfs(1,0,0); cout<<ans; return 0; }