0/1 Knapsack Problem

You are given a set of n items, each with a value and a weight. You are also given a knapsack with a weight capacity W. Your task is to determine the maximum total value of items that can be included in the knapsack without exceeding its capacity.

This is a classic 0/1 Knapsack Problem that can be solved using dynamic programming. The recurrence relation is given by:

$$ dp[i][w] = \max( dp[i-1][w],\ dp[i-1][w-\text{weight}_i]+\text{value}_i )$$

with the base case defined as dp[0][*] = 0 and dp[*][0] = 0. The expected time complexity is $O(n \times W)$ and the space complexity is $O(n \times W)$.

inputFormat

The input is read from standard input (stdin). The first line contains two integers n and W, representing the number of items and the knapsack capacity, respectively. Each of the next n lines contains two integers representing the value and the weight of an item.

 n W
 value1 weight1
 value2 weight2
 ...
 valuen weightn

outputFormat

Output a single integer representing the maximum value that can be obtained without exceeding the knapsack's capacity. The output is printed to standard output (stdout).

0 10

0