0/1 Knapsack Problem: Maximum Total Value

You are given a collection of items, each with a specified weight and value. Your task is to determine the maximum total value that can be carried by Suzuki without exceeding a given weight limit.

Input Format: The first line of the input contains two integers, n and W, where n is the number of items and W is the weight limit. This is followed by n lines, each containing two integers, representing the weight and value of each item.

Output Format: Output a single integer representing the maximum total value that can be obtained without exceeding the weight limit.

The problem can be formulated using dynamic programming. The recurrence relation for computing the answer is given by:

\[ dp[i][w] = \begin{cases} \max(dp[i-1][w], dp[i-1][w - weight_i] + value_i) & \text{if } weight_i \leq w,\\ dp[i-1][w] & \text{if } weight_i > w. \end{cases} \]

where \(dp[i][w]\) is the maximum value achievable with the first \(i\) items and a capacity of \(w\).

inputFormat

The first line contains two space-separated integers: n (the number of items) and W (the weight limit). Each of the next n lines contains two space-separated integers: the weight and value of an item.

outputFormat

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

## sample

4 5
2 3
3 4
4 5
5 8

8

</p>