Knapsack of Ores

You are given n different types of ores. Each ore type has a specific weight and value. You have a bag that can carry a maximum weight W. The task is to select a subset of these ores such that the total weight does not exceed W and the total value is maximized.

This is a classic 0/1 Knapsack problem where each ore can either be taken or not taken. The optimal solution can be computed using dynamic programming with the recurrence:

[ dp[w] = \max( dp[w],; dp[w - weight] + value ) \quad \text{for } w \geq weight ]

Note that the solution should work efficiently for the given constraints.

inputFormat

The first line contains two integers n and W, where n is the number of different types of ores and W is the maximum weight capacity of the bag.

This is followed by n lines. Each of these lines contains two integers representing the weight and value of each ore respectively.

You need to read input from standard input (stdin).

outputFormat

Output a single integer representing the maximum total value of ores that can be carried in the bag without exceeding the weight limit.

The output should be written to standard output (stdout).

## sample

4 10
5 10
4 40
6 30
3 50

90