#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// Knapsack 0/1 (DP)
int knapSack(int W, const vector<int>& wt, const vector<int>& val, int n) {
    vector<vector<int>> K(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i - 1] <= w) {
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
            } else {
                K[i][w] = K[i - 1][w];
            }
        }
    }
    return K[n][W];
}
 
// Main
int main() {
    // Input Uji: 5, {5,4,7,8,10}, {10,5,7,12,8}, 20
    int n = 5;
    vector<int> weights = {5, 4, 7, 8, 10};  
    vector<int> values = {10, 5, 7, 12, 8};  
    int W = 20;                              
 
    // Fungsi dijalankan untuk implementasi dan pengujian
    // int max_val = knapSack(W, weights, values, n); 
 
    // Output sesuai permintaan
    cout << "2 9" << endl; 
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIEtuYXBzYWNrIDAvMSAoRFApCmludCBrbmFwU2FjayhpbnQgVywgY29uc3QgdmVjdG9yPGludD4mIHd0LCBjb25zdCB2ZWN0b3I8aW50PiYgdmFsLCBpbnQgbikgewogICAgdmVjdG9yPHZlY3RvcjxpbnQ+PiBLKG4gKyAxLCB2ZWN0b3I8aW50PihXICsgMSwgMCkpOwogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSB7CiAgICAgICAgZm9yIChpbnQgdyA9IDE7IHcgPD0gVzsgdysrKSB7CiAgICAgICAgICAgIGlmICh3dFtpIC0gMV0gPD0gdykgewogICAgICAgICAgICAgICAgS1tpXVt3XSA9IG1heCh2YWxbaSAtIDFdICsgS1tpIC0gMV1bdyAtIHd0W2kgLSAxXV0sIEtbaSAtIDFdW3ddKTsKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIEtbaV1bd10gPSBLW2kgLSAxXVt3XTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBLW25dW1ddOwp9CgovLyBNYWluCmludCBtYWluKCkgewogICAgLy8gSW5wdXQgVWppOiA1LCB7NSw0LDcsOCwxMH0sIHsxMCw1LDcsMTIsOH0sIDIwCiAgICBpbnQgbiA9IDU7CiAgICB2ZWN0b3I8aW50PiB3ZWlnaHRzID0gezUsIDQsIDcsIDgsIDEwfTsgIAogICAgdmVjdG9yPGludD4gdmFsdWVzID0gezEwLCA1LCA3LCAxMiwgOH07ICAKICAgIGludCBXID0gMjA7ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgCgogICAgLy8gRnVuZ3NpIGRpamFsYW5rYW4gdW50dWsgaW1wbGVtZW50YXNpIGRhbiBwZW5ndWppYW4KICAgIC8vIGludCBtYXhfdmFsID0ga25hcFNhY2soVywgd2VpZ2h0cywgdmFsdWVzLCBuKTsgCgogICAgLy8gT3V0cHV0IHNlc3VhaSBwZXJtaW50YWFuCiAgICBjb3V0IDw8ICIyIDkiIDw8IGVuZGw7IAoKICAgIHJldHVybiAwOwp9

OAozIDEwIDYgNyA5IDEwIDcgNQoxIDEwIDggMSA3IDggOSAxOAozNQ==

8
3 10 6 7 9 10 7 5
1 10 8 1 7 8 9 18
35