벼락치기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 문제를 푸는 데 걸리는 일수와 벌금이 주어질 때, T일 안에 일부 문제를 골라 풀어 남은 문제의 벌금 합을 최소로 만든다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 그리디, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

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

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


	해결하는 데 소요되는 일수	벌금
문제1	2	5000
문제2	1	1000
문제3	1	2000

예를 들어, 프로그래밍 과제로 위와 같이 $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$ 을 출력한다.

예제3

예제 1
입력
```
3 3
2 5000
1 1000
1 2000
```
예상 출력
```
1000
```
예제 2
입력
```
4 5
2 5000
2 2000
2 3000
3 1000
```
예상 출력
```
3000
```
예제 3
입력
```
3 6
1 1000
2 4000
3 2000
```
예상 출력
```
0
```