Maximize Total Value

You are given a set of items. Each item has an associated cost and value. You are also given an integer \(C\) representing the maximum cost you can spend. Your task is to select a subset of these items such that the total cost does not exceed \(C\) and the total value is maximized.

This is a classic 0/1 knapsack problem where each item can be selected at most once. The problem can be formulated using the following recurrence relation in dynamic programming:

\(dp[j] = \max\{ dp[j], dp[j - cost] + value \}\) for all \(j\) from \(C\) down to \(cost\), where cost and value are from the current item.

inputFormat

The first line of the input contains two integers n and C separated by space, where n is the number of items and C is the maximum cost allowed.

Each of the following n lines contains two integers: the cost and the value of an item.

It is guaranteed that all numbers are non-negative.

outputFormat

Output a single integer representing the maximum total value that can be achieved without exceeding the cost \(C\).

4 8
4 6
2 4
6 7
5 10

14