Maximum Problem Score

You are given a list of problems. Each problem is represented by a pair of integers: the first integer is the score you earn for solving the problem, and the second integer is the time required to solve it. You have a total available time T and you want to maximize your score by choosing a subset of problems to solve such that the sum of their solving times does not exceed T.

This is a classic Knapsack problem where each problem is an item with a value (score) and weight (time), and you want to maximize the total value without exceeding the capacity (time limit).

Input and Output: The input is read from stdin and the output is printed to stdout. See the input and output descriptions for details.

inputFormat

The input is given via standard input (stdin). The first line contains two integers n and T, where n is the number of problems and T is the total available time. Each of the following n lines contains two integers: the first is the score of a problem and the second is the time required to solve that problem.

outputFormat

Output a single integer to standard output (stdout), representing the maximum total score that can be achieved without exceeding the total time T.## sample

4 5
10 2
20 2
30 3
40 4

50