Gena is the genius of sports programming. He can solve any problem, so he has never lost a contest. Today Gena decided to write the contest badly on purpose, because he was tired to take always the first place.

But Gena cannot simply not to submit the problems at the contest, as this can be called unsportsmanlike behavior. Therefore, he decided to choose an unsuccessful problem solving strategy, namely, he wants to hand over problems in such a way as to score as few points as possible.

The contest consists of n problems, numbered from 1 to n. For solving the problem i, the participant receives pi points. Gena reads all problems and immediately came up with a solution for each. Also, for each task, he estimated the time it would take him to write a solution for this task: task i requires ti minutes for Gena to solve. It remains to choose the order in which he will write solutions. Looking at his watch, Gena realized that t minutes left until the end of the contest.

Gena plans to act as follows. He selects one of the previously unsolved problems and writes down its solution in the appropriate time. Gena never chooses a problem that he cannot write until the end of the contest. After writing the solution, he immediately sends the problem for verification and receives pi points for it. Time is not wasted on sending and checking the solution. After that, he moves on to another task. As soon as Gena realizes that he will not have time to write any of the remaining problems until the end of the contest, he stops writing solutions.

Now Gena wants to choose the order of writing problems that will minimize his total score for the contest. Help Gena to determine the minimum possible total score he can get by following the procedure described.

Input

The first line contains two integers n and t (1 ≤ n, t ≤ 2000) - number of problems and time until the end of the contest in minutes.

The following n lines describe the tasks, i - th line contains two numbers ti, pi (1 ≤ ti ≤ 2000, 1 ≤ pi ≤ 106) - the time it takes for Gena to write a solution for this problem, and the number of points the participant gets for solving this problem.

Output

Print one number - the minimum number of points that Gena can get in the contest.