#include <iostream>
using namespace std;
 
int knapsack (int W, int wt[], int val[], int n) {
  //Base case
  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[] = {60, 100, 120};
  int wt[] = {10, 20, 30};
  int W = 50, n = 3;
  printf("%d", knapsack(W, wt, val, n));
  return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGtuYXBzYWNrIChpbnQgVywgaW50IHd0W10sIGludCB2YWxbXSwgaW50IG4pIHsKICAvL0Jhc2UgY2FzZQogIGlmIChuID09IDAgfHwgVyA9PSAwKSB7CiAgICByZXR1cm4gMDsKICB9IAogIGlmICh3dFtuLTFdID4gVykgewogICAgcmV0dXJuIGtuYXBzYWNrKFcsIHd0LCB2YWwsIG4tMSk7CiAgfSBlbHNlIHsKICAgIHJldHVybiBtYXggKCh2YWxbbi0xXSArIGtuYXBzYWNrKFctd3Rbbi0xXSwgd3QsIAogICAgICAgICAgICAgICAgIHZhbCwgbi0xKSksIGtuYXBzYWNrKFcsIHd0LCB2YWwsIG4tMSkpOwogIH0KfQoKaW50IG1haW4gKCkgewogIGludCB2YWxbXSA9IHs2MCwgMTAwLCAxMjB9OwogIGludCB3dFtdID0gezEwLCAyMCwgMzB9OwogIGludCBXID0gNTAsIG4gPSAzOwogIHByaW50ZigiJWQiLCBrbmFwc2FjayhXLCB3dCwgdmFsLCBuKSk7CiAgcmV0dXJuIDA7Cn0K