题解 | #点菜问题#

#include <iostream>
using namespace std;

const int N = 110;
int cost[N], score[N];
int f[N][1010];

int main() {
    int c, n;
    while (cin >> c >> n) {
        for (int i = 1; i <= n; i++) cin >> cost[i] >> score[i];

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= c; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= cost[i])
                    f[i][j] = max(f[i - 1][j], f[i - 1][j - cost[i]] + score[i]);
            }
        }
        cout << f[n][c] << endl;
    }
    return 0;
}