#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// Fungsi Knapsack 0/1 menggunakan Pemrograman Dinamis
int knapsack(int W, const vector<int>& weights, const vector<int>& values, int n) {
    // Tabel DP: dp[i][w] = nilai maksimum dengan i item dan kapasitas w
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
 
    for (int i = 1; i <= n; i++) {
        int w_i = weights[i - 1]; // Berat item saat ini
        int v_i = values[i - 1];  // Nilai item saat ini
        for (int w = 1; w <= W; w++) {
            // Default: tidak memasukkan item (nilai dari baris sebelumnya)
            dp[i][w] = dp[i - 1][w]; 
 
            // Jika item muat, bandingkan dengan memasukkannya
            if (w_i <= w) {
                dp[i][w] = max(dp[i][w], v_i + dp[i - 1][w - w_i]);
            }
        }
    }
    return dp[n][W]; // Nilai maksimum total
}
 
// Pengujian Singkat
int main() {
    // Data Uji Coba:
    vector<int> values = {60, 100, 120}; // Nilai
    vector<int> weights = {10, 20, 30};  // Berat
    int W = 50;                          // Kapasitas
    int n = values.size();               // Jumlah Item
 
    cout << "Kapasitas Knapsack (W): " << W << endl;
 
    // Hitung dan tampilkan hasilnya
    int max_value = knapsack(W, weights, values, n);
 
    cout << "Nilai Maksimum: **" << max_value << "**" << endl;
    // Hasilnya 220, dari item (100/20) dan (120/30). Total berat 50.
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIEZ1bmdzaSBLbmFwc2FjayAwLzEgbWVuZ2d1bmFrYW4gUGVtcm9ncmFtYW4gRGluYW1pcwppbnQga25hcHNhY2soaW50IFcsIGNvbnN0IHZlY3RvcjxpbnQ+JiB3ZWlnaHRzLCBjb25zdCB2ZWN0b3I8aW50PiYgdmFsdWVzLCBpbnQgbikgewogICAgLy8gVGFiZWwgRFA6IGRwW2ldW3ddID0gbmlsYWkgbWFrc2ltdW0gZGVuZ2FuIGkgaXRlbSBkYW4ga2FwYXNpdGFzIHcKICAgIHZlY3Rvcjx2ZWN0b3I8aW50Pj4gZHAobiArIDEsIHZlY3RvcjxpbnQ+KFcgKyAxLCAwKSk7CgogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSB7CiAgICAgICAgaW50IHdfaSA9IHdlaWdodHNbaSAtIDFdOyAvLyBCZXJhdCBpdGVtIHNhYXQgaW5pCiAgICAgICAgaW50IHZfaSA9IHZhbHVlc1tpIC0gMV07ICAvLyBOaWxhaSBpdGVtIHNhYXQgaW5pCiAgICAgICAgZm9yIChpbnQgdyA9IDE7IHcgPD0gVzsgdysrKSB7CiAgICAgICAgICAgIC8vIERlZmF1bHQ6IHRpZGFrIG1lbWFzdWtrYW4gaXRlbSAobmlsYWkgZGFyaSBiYXJpcyBzZWJlbHVtbnlhKQogICAgICAgICAgICBkcFtpXVt3XSA9IGRwW2kgLSAxXVt3XTsgCgogICAgICAgICAgICAvLyBKaWthIGl0ZW0gbXVhdCwgYmFuZGluZ2thbiBkZW5nYW4gbWVtYXN1a2thbm55YQogICAgICAgICAgICBpZiAod19pIDw9IHcpIHsKICAgICAgICAgICAgICAgIGRwW2ldW3ddID0gbWF4KGRwW2ldW3ddLCB2X2kgKyBkcFtpIC0gMV1bdyAtIHdfaV0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIGRwW25dW1ddOyAvLyBOaWxhaSBtYWtzaW11bSB0b3RhbAp9CgovLyBQZW5ndWppYW4gU2luZ2thdAppbnQgbWFpbigpIHsKICAgIC8vIERhdGEgVWppIENvYmE6CiAgICB2ZWN0b3I8aW50PiB2YWx1ZXMgPSB7NjAsIDEwMCwgMTIwfTsgLy8gTmlsYWkKICAgIHZlY3RvcjxpbnQ+IHdlaWdodHMgPSB7MTAsIDIwLCAzMH07ICAvLyBCZXJhdAogICAgaW50IFcgPSA1MDsgICAgICAgICAgICAgICAgICAgICAgICAgIC8vIEthcGFzaXRhcwogICAgaW50IG4gPSB2YWx1ZXMuc2l6ZSgpOyAgICAgICAgICAgICAgIC8vIEp1bWxhaCBJdGVtCgogICAgY291dCA8PCAiS2FwYXNpdGFzIEtuYXBzYWNrIChXKTogIiA8PCBXIDw8IGVuZGw7CiAgICAKICAgIC8vIEhpdHVuZyBkYW4gdGFtcGlsa2FuIGhhc2lsbnlhCiAgICBpbnQgbWF4X3ZhbHVlID0ga25hcHNhY2soVywgd2VpZ2h0cywgdmFsdWVzLCBuKTsKICAgIAogICAgY291dCA8PCAiTmlsYWkgTWFrc2ltdW06ICoqIiA8PCBtYXhfdmFsdWUgPDwgIioqIiA8PCBlbmRsOwogICAgLy8gSGFzaWxueWEgMjIwLCBkYXJpIGl0ZW0gKDEwMC8yMCkgZGFuICgxMjAvMzApLiBUb3RhbCBiZXJhdCA1MC4KCiAgICByZXR1cm4gMDsKfQ==

NQo1IDQgNyA4IDEwCjEwIDUgNyAxMiA4CjIw

5
5 4 7 8 10
10 5 7 12 8
20