#include <iostream>
using namespace std;

int knapsack (int W, int wt[], int val[], int n) {
  int K[n+1][W+1] = {0};

  // Building table K[][] in bottom manner
  for(int i=0; i<=n; i++) {
    for(int w=0; w <= W; w++) {
      // Base case: empty knapsack
      if (i == 0 || w == 0) {
        K[i][w] = 0;
      } else if (wt[i-1] <= w) {
        // Selecting val[i-1] if it gives higher
        // knapsack value
        K[i][w] = max((val[i-1] + K[i-1][w-wt[i-1]]),
                   K[i-1][w]);
      } else {
        // Not including val[i-1]: 
        // if wt[i-1] is greater than 
        // available knapsack capacity
        K[i][w] = K[i-1][w];
      }
    }
  }
  return K[n][W];
}
 

int main() {
	// your code goes here
  int val[] = {60, 100, 120};
  int wt[] = {10, 20, 30};
  int W = 50, n = 3;
  printf("%d", knapsack(W, wt, val, n));
  return 0;
	return 0;
}