Problem 10: 0/1 Knapsack Problem

Problem Statement: Given a set of items, each with a weight and a value, determine the maximum value that can be achieved with a given capacity using 0/1 Knapsack Dynamic Programming.

Input

First line contains n and W, number of items and maximum capacity. Each of the next n lines contains two integers: weight and value.

Output

Print the maximum value achievable within the capacity.

Examples


Input:
4 7
6 13
4 8
3 6
5 12

Output:
14

Solution Explanation

Method 1: Use dynamic programming where dp[i][w] represents the maximum value using the first i items with capacity w; optimize by iterating backwards on weight. Method 2: Use a space optimized version that only uses a 1D dp array updated in reverse order for each item.

Solution in C++


#include 
#include 
#include 
using namespace std;

int main(){
    int n, W;
    cin >> n >> W;
    vector weight(n), value(n);
    for(int i=0;i> weight[i] >> value[i];
    }
    vector dp(W+1, 0);
    for(int i=0;i=weight[i]; w--){
            dp[w] = max(dp[w], dp[w-weight[i]] + value[i]);
        }
    }
    cout << dp[W];
    return 0;
}