Maximal Value of Items - Knapsack Problem

Marta is planning a hiking trip and wants to pack her backpack as efficiently as possible. She has a backpack with a weight capacity of \(W\) and a list of \(n\) essential items, where each item has a specific weight and value. The problem is to select a subset of these items such that the total weight does not exceed \(W\) while maximizing the total value.

This is a typical 0/1 Knapsack problem where the objective is to maximize the total value given a weight constraint. Formally, if we let \(v_i\) be the value and \(w_i\) be the weight of the \(i\)-th item, and \(S\) be the set of chosen items, we want to:

[ \text{maximize} \quad \sum_{i \in S} v_i \quad\text{subject to}\quad \sum_{i \in S} w_i \leq W ]

Your task is to implement an efficient algorithm to solve this problem.

inputFormat

The input is given via standard input (stdin) and has the following format:

 n W
 w1 v1
 w2 v2
 ...
 wn vn

Where:

• n is the number of items.
• W is the maximum capacity of the backpack.
• Each of the next n lines contains two integers: the weight \(w_i\) and the value \(v_i\) of the \(i\)-th item.

outputFormat

Output a single integer to standard output (stdout): the maximum total value that can be carried without exceeding the weight capacity.

## sample

3 50
20 40
50 100
30 60

100