题解 | 采药

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T, M;
    while (cin >> T >> M) {
        vector<int> time(T + 1, 0);
        for (int i = 0; i < M; i++) {
            int t, price;
            cin >> t >> price;
            if (t > T) continue;
            else {
                for (int j = T; j >= t; j--) {
                    time[j] = max(time[j], time[j - t] + price);
                }
            }
        }
        cout << time[T] << "\n";
    }
    return 0;
}