0-1 Knapsack Problem

You are given a knapsack (backpack) with a maximum weight capacity \(W\) and \(n\) items. Each item is characterized by its weight and value. The 0-1 Knapsack Problem asks: what is the maximum total value obtainable by selecting a subset of the items such that the sum of their weights does not exceed \(W\)?

Note: Each item can be taken at most once (i.e. you either include an item completely or not at all).

This problem is a classic example in dynamic programming. A common approach is to use a one-dimensional DP array where the state \(dp[j]\) represents the maximum value achievable with a knapsack capacity of \(j\).

inputFormat

The input is provided via stdin in the following format:

n W
w1 v1
w2 v2
... 
wn vn

Here, the first line contains two integers:\(n\) (the number of items) and \(W\) (the maximum capacity of the knapsack). Each of the next \(n\) lines contains two integers: \(w_i\) and \(v_i\), representing the weight and value of the \(i^{th}\) item respectively.

outputFormat

The output should be a single integer written to stdout representing the maximum total value that can be achieved without exceeding the knapsack's capacity.

4 7
2 10
3 20
4 30
5 40

50