Knapsack Problem

This is a classic 0/1 Knapsack Problem where you are given n stones. Each stone has a weight and a value. You need to choose a subset of these stones such that the sum of the weights does not exceed a given capacity W, and the total value is maximized.

Mathematically, let \(w_i\) and \(v_i\) denote the weight and value of the \(i\text{-th}\) stone respectively. The goal is to compute \[ \max \left\{ \sum_{i \in S} v_i \;:\; \sum_{i \in S} w_i \leq W \right\} \]

Try to implement an efficient solution using dynamic programming.

inputFormat

The first line contains two integers n and W where n is the number of stones and W is the maximum capacity. The next n lines each contain two integers representing the weight and value of each stone.

outputFormat

Output a single integer representing the maximum total value that can be carried without exceeding the capacity W.## sample

4 5
2 3
1 2
3 4
2 2

7