#include<bits/stdc++.h> #include<stdio.h> #include<conio.h> #include<time.h> #include<cmath> using namespace std; int a,b,c,d[1035],e[1004],f,g,h[1005][1005]; void print() { int x,y; for( x=1;x<=a;x++) { for( y=1;y<=b;y++) cout<<h[x][y]<<" "; cout<<endl; } } int main() { cin>>a>>b; for(c=1;c<=b;c++) cin>>d[c]>>e[c]; for(f=1;f<=b;f++) for(g=1;g<=a;g++) { if(g>=d[f]) h[f][g]=max(h[f-1][g-d[f]]+e[f],h[f-1][g]); else h[f][g]=h[f-1][g]; } cout<<h[b][a]; return 0; }