```cpp
#include<iostream>
using namespace std;
int c[500000],w[500000],f[500000];
int main()
{
int m,n;
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=w[i];v<=m;v++)
if(f[v-w[i]]+c[i]>f[v]) f[v]=f[v-w[i]]+c[i];
cout<<f[m];
return 0;
}
```
by awask @ 2017-11-02 12:55:06