0/1 Knapsack Problem

You are given N items, each with a specific weight and value, along with a backpack that can carry at most W weight. Your task is to select a subset of items such that the total weight does not exceed W and the total value is maximized. This is a classic 0/1 Knapsack problem where each item can be chosen at most once. The constraint can be formulated as: $$\sum_{i=1}^{N} w_i \cdot x_i \leq W$$, where $$x_i \in \{0, 1\}$$ indicates whether the i-th item is taken.

inputFormat

The first line of input contains two integers N and W separated by space, where N is the number of items and W is the maximum capacity of the backpack. Each of the following N lines contains two space-separated integers representing the weight and the value of an item.

outputFormat

Output a single integer representing the maximum total value that can be achieved without exceeding the weight capacity.

3 50
10 60
20 100
30 120

220