How to Fail at Programming Contest

Gennady is the best at competitive programming. He can solve any problem, so he has never lost a contest. But today he has decided to lose a contest, because winning every contest is not interesting.

Gennady cannot simply abandon solving problems, since that is unsportsmanlike behavior. So he has decided to pick a bad strategy that minimizes his total points for the contest.

There are $n$ problems in the contest, numbered from $1$ to $n$. If a contestant solves problem $i$, he gets $p\_i$ points. Gennady has read all the problems and came up with a solution for each one. He knows that for problem $i$ he needs exactly $t\_i$ minutes to write the solution. The final thing to do is to choose the order in which he writes the solutions. Gennady noticed that he has $T$ minutes remaining until the end of the contest.

Gennady wants to use the following strategy. He chooses a problem he has not solved yet and writes a solution for it. He never chooses a problem he cannot finish in time. When the solution is ready, Gennady submits it and gets $p\_i$ points for this problem. Submitting and testing take no time. Then he moves on to another problem. When Gennady realizes he cannot solve any of the remaining problems in time, he stops coding.

Now Gennady wants to choose the order of solving problems that minimizes his score for the contest. Help him find the smallest number of points he can get while following the rules above.

The first line of input contains two integers $n$ and $T$, the number of problems and the time until the end of the contest ($1 \leq n, T \leq 2000$).

The following $n$ lines describe the problems. The $i$-th line contains two integers $t\_i$, $p\_i$, the time Gennady needs to solve this problem and the number of points this problem is worth ($1 \leq t\_i \leq 2000$, $1 \leq p\_i \leq 10^6$).

Output one number: the minimal number of points Gennady can get.