题解 | #采药#

#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 1000 + 10;
const int MAXM = 100 + 10;

int dp[MAXN];
int weight[MAXM];
int value[MAXM];

int main() {
	int t, m;
	while (cin >> t >>m){
		for (int i = 1; i <= m; i++){
			cin >> weight[i] >> value[i];
		}
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= m; i++){
			for (int j = t; j >= weight[i]; j--){
				dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 
			}
		}
		cout << dp[t] << endl;
	}
	return 0;
}