每日AC

#include <iostream>
#include <vector>

using namespace std;

int main() {

int K, V, N;
cin >> K >> V >> N;
vector<int> c(N), w(N);
for (int i = 0; i < N; ++i) {
    cin >> c[i] >> w[i];
}

vector<vector<int>> dp(V + 1);
dp[0].push_back(0);

for (int i = 0; i < N; ++i) {
    int ci = c[i];
    int wi = w[i];
    for (int v = V; v >= ci; --v) {
        int prev_v = v - ci;
        if (dp[prev_v].empty()) continue;

        vector<int> temp;
        for (int val : dp[prev_v]) {
            temp.push_back(val + wi);
        }

        vector<int> merged;
        int p1 = 0, p2 = 0;
        while ((p1 < dp[v].size() || p2 < temp.size()) && merged.size() < K) {
            int val1 = (p1 < dp[v].size()) ? dp[v][p1] : -1;
            int val2 = (p2 < temp.size()) ? temp[p2] : -1;
            if (val1 > val2) {
                merged.push_back(val1);
                p1++;
            } else {
                merged.push_back(val2);
                p2++;
            }
        }
        dp[v] = merged;
    }
}

int sum = 0;
int count = min(K, (int)dp[V].size());
for (int i = 0; i < count; ++i) {
    sum += dp[V][i];
}
cout << sum << endl;

return 0;

}