0/1 Knapsack Problem

You are given a set of n boxes, where each box i has a weight w_i and a value v_i. You also have a truck that can carry at most W units of weight. Your goal is to select a subset of boxes such that the total weight does not exceed W and the total value is maximized. This is the classic 0/1 Knapsack Problem.

The problem can be formalized using the following equation:

\[ \text{dp}[w] = \max\{ \text{dp}[w],\, \text{dp}[w - w_i] + v_i \} \quad \text{for } w_i \leq w \leq W \]

It is guaranteed that the number of boxes and the maximal weight are provided as input, followed by the details of each box. Your task is to compute the maximum total value that can be achieved without exceeding the weight capacity W.

inputFormat

The first line of input contains two integers n and W separated by a space, where n is the number of boxes and W is the maximum weight capacity of the truck.

The following n lines each contain two integers separated by a space. The first integer is the weight w_i of the i-th box, and the second integer is the corresponding value v_i.

outputFormat

Output a single integer representing the maximum total value that can be achieved without exceeding the weight limit W.

4 10
5 10
4 40
6 30
3 50

90