#include<iostream> #include<cstdio> using namespace std; int m,n; int w[10005],c[10005]; int f[10005]; int main() { cin>>m>>n; for(int i=1;i<=n;i++){ cin>>w[i]>>c[i]; } for(int i=1;i<=n;i++){ for(int v=m;v>=w[i];v--){ if(f[v-w[i]]+c[i]>f[v]){ f[v]=f[v-w[i]]+c[i]; cout<<endl; } } } cout<<f[m]<<endl; return 0; /* 8 3 2 3 5 4 5 5 */ /* f f v w v v v w w 8 2 6 0 3 8 5 3 3 7 8 5 3 3 8 7 2 5 0 3 7 5 2 3 7 7 5 2 3 8 6 2 4 0 3 6 5 1 0 6 5 1 0 5 2 3 0 3 5 5 0 0 5 5 0 0 4 2 2 0 3 3 2 1 0 3 2 2 0 0 3 */ }