#include<bits/stdc++.h> using namespace std; long long m,n,ans=0; struct st { long long c,w; }f[1097]; long long d[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)dfs(i+1,f[i].w+wi,f[i].c+ci); dfs(i+1,wi,ci); } int main() { cin>>m>>n; for(int i=1;i<=n;i++) { cin>>f[i].w>>f[i].c; } dfs(1,0,0); cout<<ans; return 0; }