29704번 - 벼락치기

숙명여자대학교의 알고리즘 학회 ALGOS에 합격한 혜민이는 너무 기뻐 마음이 들뜬 나머지 프로그래밍 과제가 있는 것을 잊어버리고 말았다. 프로그래밍 과제로는 다양한 난이도의 문제 $N$개가 주어지고, 앞으로 $T$일의 제출 기한이 남아있다. 만약 제출 기한 내에 문제를 제출 못 하면, 제출하지 못한 문제마다 정해져 있는 벌금을 내야 한다. 혜민이는 벌금을 내고 싶지 않기 때문에, 내는 벌금의 총금액이 가능한 한 적어지도록 문제를 풀려고 한다.

문제를 해결하는 데 소요되는 일수와 그 문제를 제출 기한 내에 해결하지 못할 경우 내야 하는 벌금이 주어질 때, 혜민이가 내야 하는 벌금의 최소 금액을 구해보자. 제출 기한 $T$일이 지났을 때, 제출하지 못한 문제별 벌금의 합이 혜민이가 최종적으로 내야 하는 벌금이다. 단, 혜민이는 아직 프로그래밍에 익숙하지 않아서 한 번에 한 개의 문제만 해결할 수 있다.

예를 들어, 프로그래밍 과제로 위와 같이 $3$개의 문제가 주어졌다고 가정해 보자. 제출 기한이 $3$일 남았다면, 첫째 날에 $3$번 문제를 해결하고, 둘째 날과 셋째 날에 걸쳐 $1$번 문제를 해결하면 $2$번 문제의 벌금인 $1\,000$원만 내면 된다.

혜민이가 가능한 한 적은 벌금을 낼 수 있게 도와주자.

첫째 줄에 문제의 개수 $N(1 \leq N \leq 1\,000)$과 남은 제출 기한 $T(1 \leq T \leq 1\,000)$가 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐 $i$번 문제를 푸는 데 걸리는 일수 $d_i$$(1 \leq d_i \leq 1\,000)$와 해당 문제의 벌금 $m_i$$(1 \leq m_i \leq 5\,000)$이 주어진다.

최종적으로 내는 벌금이 최소가 되도록 문제를 풀었을 때, 혜민이가 내야 하는 벌금을 출력한다.

만약, 기한 내에 모든 문제를 해결할 수 있다면 $0$을 출력한다.