- include<cstdio>
- include<algorithm>
using namespace std; const int N=1e3+1; int n,m,v[N],c[N]; //从第i个物品开始挑选总重量不大于sumv的部分 int dfs(int now,int sumv){
int res; if(now==n+1) return res=0;//已经没有剩余物品 if(sumv<v[now]) res=dfs(now+1,sumv);//无法挑选第i个物品 else res=max(dfs(now+1,sumv),dfs(now+1,sumv-v[now])+c[now]);//比较挑和不挑的情况，选取最大的情况 return res;
} int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&c[i]);
printf("%d",dfs(1,m));
return 0;
}