프로그래밍 대회에서 지는 법

Gennady는 경쟁 프로그래밍 최강자다. 어떤 문제든 풀 수 있어서 대회에서 한 번도 진 적이 없다. 그런데 모든 대회에서 우승하는 것도 재미가 없다고 생각한 그는 오늘은 일부러 한 대회에서 지기로 마음먹었다.

그렇다고 해서 문제를 풀지 않고 버리는 것은 비신사적인 행동이라 할 수 없다. 그래서 그는 그냥 대회에서 얻는 총점을 최소로 만드는 나쁜 전략을 선택하기로 했다.

대회에는 $1$번부터 $n$번까지 번호가 붙은 $n$개의 문제가 있다. 참가자가 $i$번 문제를 풀면 $p\_i$점을 얻는다. Gennady는 모든 문제를 읽고 각 문제에 대한 풀이를 떠올려 두었다. $i$번 문제의 풀이를 작성하는 데 정확히 $t\_i$분이 걸린다는 것도 알고 있다. 이제 남은 일은 문제 풀이를 작성할 순서를 정하는 것이다. Gennady는 대회가 끝날 때까지 $T$분이 남아 있다는 것을 알아차렸다.

Gennady는 다음과 같은 전략을 쓰려고 한다. 아직 풀지 않은 문제 하나를 골라 그 풀이를 작성한다. 시간 안에 끝낼 수 없는 문제는 절대 고르지 않는다. 풀이가 완성되면 제출해서 그 문제의 $p\_i$점을 받는다. 제출과 채점에는 시간이 걸리지 않는다. 그런 다음 다른 문제로 넘어간다. 남은 문제 중 시간 안에 풀 수 있는 것이 하나도 없다고 판단하면 코딩을 멈춘다.

이제 Gennady는 대회에서 얻는 점수를 최소로 만드는 문제 풀이 순서를 정하려고 한다. 위 규칙을 따를 때 그가 얻을 수 있는 최소 점수를 구해 보자.

첫째 줄에 문제의 수와 대회가 끝날 때까지 남은 시간을 나타내는 두 정수 $n$과 $T$가 주어진다 ($1 \leq n, T \leq 2000$).

다음 $n$개 줄에 문제에 대한 정보가 주어진다. $i$번째 줄에는 Gennady가 이 문제를 푸는 데 필요한 시간과 이 문제가 주는 점수를 나타내는 두 정수 $t\_i$, $p\_i$가 주어진다 ($1 \leq t\_i \leq 2000$, $1 \leq p\_i \leq 10^6$).

Gennady가 얻을 수 있는 최소 점수를 출력한다.