Maximum Rating Within Budget

You are given N items, each with a price and a rating. You are also provided with a budget B. Your task is to select a subset of these items so that the total price does not exceed the budget while maximizing the overall rating.

This is a variation of the 0/1 Knapsack problem where each item has a cost (price) and a benefit (rating). If no items can be chosen within the given budget, the output should be 0.

The optimal solution can be calculated by dynamic programming. The recurrence relation can be represented in LaTeX as follows:

\( dp[b] = \max\bigl(dp[b],\; dp[b - \text{price}] + \text{rating}\bigr) \) for each item and for budgets \( b \) going from \( B \) down to \( \text{price} \).

inputFormat

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

1. The first line contains two integers N (the number of items) and B (the budget), separated by a space.
2. The next N lines each contain two integers representing the price and rating of an item, separated by a space.

outputFormat

Output a single integer representing the maximum total rating that can be achieved without exceeding the budget. The output should be printed to standard output.

4 100
20 8
50 9
30 5
70 7

22