Knapsack Problem

You are given a knapsack with a weight capacity \(W\) and \(N\) items. Each item has a specified weight and value. Your task is to select a subset of these items such that the total weight does not exceed \(W\) and the total value is maximized. If no items can be taken, the answer is 0.

This is the classic 0/1 Knapsack Problem where each item can either be taken or left.

inputFormat

The input is given via standard input (stdin). The first line contains two integers (N) and (W) representing the number of items and the knapsack's weight capacity, respectively. Each of the following (N) lines contains two integers: the weight and the value of an item.

outputFormat

Output a single integer to standard output (stdout): the maximum total value achievable without exceeding the weight capacity.## sample

4 5
2 3
1 2
3 4
2 2

7