#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int knapSack(int W, int wt[], int val[], int n) {
    if (n == 0 || W == 0) {
        return 0;
    }

    if (wt[n - 1] > W) {
        return knapSack(W, wt, val, n - 1);
    } else {
        return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1));
    }
}

int main() {
    int val[] = {2000, 1500, 2000,3000};
    int wt[] = {1,1,3,4};
    int W = 4;
    int n = sizeof(val) / sizeof(val[0]);

    int result = knapSack(W, wt, val, n);
    printf("Maximum value: %d\n", result);

    return 0;
}