题目

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,m,w[10005],v[10005],dp[10000005]/*dp[i][j]表示前i种草药用j时间采完的最大价值*/;
//dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]*k]+v[i]*k) 
signed main()
{
	scanf("%d%d",&t,&m);
	for(int i=1;i<=m;i++)scanf("%d%d",&w[i],&v[i]);
	for(int i=1;i<=m;i++)
		for(int j=w[i];j<=t;j++)
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
	printf("%d\n",dp[t]);
	return 0;
}