#include<bits/stdc++.h> using namespace std; int m,n; int a[35],c[35],f[35]; void z(int cost,int w){ for(int v= w;v<=m;v++){ f[v] = max(f[v],f[v-w]+cost); } } int main(){ cin>>m>>n; for(int i = 1;i<=n;i++){ cin>>a[i]>>c[i]; } for(int i = 1;i<=n;i++){ z(c[i],a[i]); } cout<<"max="<<f[m]<<endl; return 0; }