题解

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

int main() {
    int m,n;
    cin >> n >> m;
    vector<int> costs(m);
    vector<int> values(m);
    for(int i = 0;i < m;i ++) {
        cin >> costs[i] >> values[i];
    }
    vector<int> dp(n + 1, 0);
    for(int i = 0;i < m;i ++) {
        for(int j = costs[i]; j <= n;j ++) {
            dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);
            //cout << dp[j] << " ";
        }
    }
    cout << dp[N];
    return 0;
}