题解 | 采药

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

int main() {
    int t, m;
    while (cin >> t >> m) { // 注意 while 处理多个 case
        vector<int> time(m), price(m);
        for (int i = 0; i < m; i++) {
            cin >> time[i] >> price[i];
        }
        vector<int> dp(t + 1, 0);
        for (int i = 0; i < m; i++) {
            int ti = time[i], p = price[i];
            for (int j = t; j >= ti; j--) {
                dp[j] = max(dp[j], dp[j - ti] + p);
            }
        }
        cout << dp[t] << endl;
    }
}
// 64 位输出请用 printf("%lld")