0-1 Knapsack Problem

You are given a knapsack with a maximum weight capacity \(W\) and \(n\) items, each described by a weight and a value. Your task is to determine the maximum total value of items that can be placed into the knapsack without exceeding its capacity.

Formally, given \(n\) items where the \(i\)th item has weight \(w_i\) and value \(v_i\), find the maximum value \(V\) such that the sum of weights of the selected items is at most \(W\). This is a classic 0-1 Knapsack problem solved using dynamic programming.

inputFormat

The first line contains two space-separated integers \(n\) and \(W\), where \(n\) is the number of items and \(W\) is the maximum capacity of the knapsack. Each of the following \(n\) lines contains two integers representing the weight and value of an item.

outputFormat

Output a single integer, the maximum total value that can be achieved without exceeding the knapsack's capacity.

4 7
1 1
3 4
4 5
5 7

9