题解 | #采药#

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

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

int dp[MAXM];
int w[MAXN];
int v[MAXN];

int main(){
	int m, n;
	while(scanf("%d%d", &m, &n) != EOF){
		for(int i=1; i<=n; i++){
			scanf("%d%d", &w[i], &v[i]);
		}
		memset(dp, 0, sizeof(dp));
		for(int i=1; i<=n; i++){
			for(int j=m; j>=w[i]; j--){
				dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
			}
		}
		printf("%d\n", dp[m]);
	}
	return 0;
}