```cpp
#include<iostream>
using namespace std;
int main()
{
int m,n;
int lm[3111]={0},ln[3111]={0},l[5555]={0};
cin>>m>>n;
for (int i=1;i<=n;i++)
cin>>lm[i]>>ln[i];
for (int i=1;i<=n;i++)
for(int k=m;k>=lm[i];k--)
if (l[k-lm[i]]+ln[i]>l[k])
l[k]=l[k-lm[i]]+ln[i];
cout<<l[m]<<endl;
return 0;
}
```
by Sn_Eddy @ 2017-06-27 16:41:58