벼락치기

면접 대비

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

요약

문제별 풀이 일수와 벌금이 주어질 때, T일 안에 풀 문제를 골라 풀지 못한 문제의 벌금 합을 최소로 만드는 값을 구합니다.

난이도: 보통10점 중 4점
유형: 동적 계획법
정답자: 아직 제출이 없습니다

문제

숙명여자대학교의 알고리즘 학회 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
```