#include <iostream>
#include <vector>
using namespace std;

// Recursive function to find the maximum value
int knapsackRecursive(int capacity, vector<int>& weights, vector<int>& values, int n) {
    // Base case: no items left or capacity becomes 0
    if (n == 0 || capacity == 0) {
        return 0;
    }

    // If the weight of the nth item is more than the capacity, skip this item
    if (weights[n - 1] > capacity) {
        return knapsackRecursive(capacity, weights, values, n - 1);
    } else {
        // Include the nth item or exclude it
        int includeItem = values[n - 1] + knapsackRecursive(capacity - weights[n - 1], weights, values, n - 1);
        int excludeItem = knapsackRecursive(capacity, weights, values, n - 1);
        return max(includeItem, excludeItem);
    }
}

int main() {
    int n; // Number of items
    int capacity; // Maximum weight capacity of the knapsack

    // Example input
    cout << "Enter number of items: ";
    cin >> n;
    cout << "Enter knapsack capacity: ";
    cin >> capacity;

    vector<int> weights(n);
    vector<int> values(n);

    cout << "Enter weights of items: ";
    for (int i = 0; i < n; i++) {
        cin >> weights[i];
    }

    cout << "Enter values of items: ";
    for (int i = 0; i < n; i++) {
        cin >> values[i];
    }

    int maxValue = knapsackRecursive(capacity, weights, values, n);
    cout << "Maximum value in the knapsack: " << maxValue << endl;

    return 0;
}