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