题解 | #采药#

#include <bits/stdc++.h>
#define MAX 1000
using namespace std;

int main() {
    int T, M, dp[MAX], i, j, v[MAX], w[MAX];
    cin >> T >> M;
    for (i = 1; i <= M; i++)
        cin >> w[i] >> v[i];
    memset(dp, 0, sizeof(dp));

    for (i = 1; i <= M; i++)
        for (j = T; j >= w[i]; j--) {
            dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
        }
    cout << dp[T];
}