#include <iostream>
using namespace std;
 
int main() {
    int n, kapasitas;
    cout << "Masukkan jumlah barang: ";
    cin >> n;
 
    int berat[10], nilai[10];
    for (int i = 0; i < n; i++) {
        cout << "Barang ke-" << i+1 << " (berat dan nilai): ";
        cin >> berat[i] >> nilai[i];
    }
 
    cout << "Masukkan kapasitas tas: ";
    cin >> kapasitas;
 
    int maxNilai = 0;
    // Coba semua kombinasi barang (versi sederhana)
    for (int i = 0; i < (1 << n); i++) {
        int totalBerat = 0, totalNilai = 0;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                totalBerat += berat[j];
                totalNilai += nilai[j];
            }
        }
        if (totalBerat <= kapasitas && totalNilai > maxNilai)
            maxNilai = totalNilai;
    }
 
    cout << "\nNilai maksimum yang bisa dibawa: " << maxNilai << endl;
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CiAgICBpbnQgbiwga2FwYXNpdGFzOwogICAgY291dCA8PCAiTWFzdWtrYW4ganVtbGFoIGJhcmFuZzogIjsKICAgIGNpbiA+PiBuOwoKICAgIGludCBiZXJhdFsxMF0sIG5pbGFpWzEwXTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICAgICAgY291dCA8PCAiQmFyYW5nIGtlLSIgPDwgaSsxIDw8ICIgKGJlcmF0IGRhbiBuaWxhaSk6ICI7CiAgICAgICAgY2luID4+IGJlcmF0W2ldID4+IG5pbGFpW2ldOwogICAgfQoKICAgIGNvdXQgPDwgIk1hc3Vra2FuIGthcGFzaXRhcyB0YXM6ICI7CiAgICBjaW4gPj4ga2FwYXNpdGFzOwoKICAgIGludCBtYXhOaWxhaSA9IDA7CiAgICAvLyBDb2JhIHNlbXVhIGtvbWJpbmFzaSBiYXJhbmcgKHZlcnNpIHNlZGVyaGFuYSkKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgKDEgPDwgbik7IGkrKykgewogICAgICAgIGludCB0b3RhbEJlcmF0ID0gMCwgdG90YWxOaWxhaSA9IDA7CiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBuOyBqKyspIHsKICAgICAgICAgICAgaWYgKGkgJiAoMSA8PCBqKSkgewogICAgICAgICAgICAgICAgdG90YWxCZXJhdCArPSBiZXJhdFtqXTsKICAgICAgICAgICAgICAgIHRvdGFsTmlsYWkgKz0gbmlsYWlbal07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgaWYgKHRvdGFsQmVyYXQgPD0ga2FwYXNpdGFzICYmIHRvdGFsTmlsYWkgPiBtYXhOaWxhaSkKICAgICAgICAgICAgbWF4TmlsYWkgPSB0b3RhbE5pbGFpOwogICAgfQoKICAgIGNvdXQgPDwgIlxuTmlsYWkgbWFrc2ltdW0geWFuZyBiaXNhIGRpYmF3YTogIiA8PCBtYXhOaWxhaSA8PCBlbmRsOwogICAgcmV0dXJuIDA7Cn0K

NQo1IDQgNyA4IDEwCjEwIDUgNyAxMiA4CjIw

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