17 lines
316 B
C++
17 lines
316 B
C++
#include<cstdio>
|
|
#include<iostream>
|
|
#include<cstdlib>
|
|
using namespace std;
|
|
long n,m,i,x,k,w[10001],c[10001],f[10001];
|
|
int main()
|
|
{
|
|
f[0]=0;
|
|
cin>>m>>n;
|
|
for (i=1; i<=n; i++) cin>>c[i]>>w[i];
|
|
|
|
for (i=1; i<=n; i++)
|
|
for (x=w[i]; x<=m; x++)
|
|
if (f[x-w[i]]+c[i]>f[x]) f[x]=f[x-w[i]]+c[i];
|
|
cout<<f[m];
|
|
}
|