#include<bits/stdc++.h> using namespace std; const int maxm = 2001,maxn = 31; int n,m,v,i; int c[maxn],w[maxm]; int f[maxm]; int main(){ cin>>m>>n; for(i = 1;i <= n;i++){ cin>>w[i]>>c[i]; } for(i = 1;i <= n;i++){ for(v = w[i];v <= m;v++){ if(f[v - w[i]] + c[i] > f[v]){ f[v] = f[v - w[i]] + c[i]; } } } printf("max=%d\n",f[m]); return 0; //共产主义万岁 //creative by yidao }