은행 대기열

면접 대비

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

요약

각 마감 시각 전에 분당 최대 한 명을 골라 모으는 현금 합계를 최대로 합니다.

난이도: 보통10점 중 5점
유형: 그리디, 힙, 정렬
정답자: 아직 제출이 없습니다

문제

올리버는 은행 지점장이고 오늘 영업을 곧 끝내려 한다. 은행이 금리를 42퍼센트 올렸다는 소식(연 0.01퍼센트에서 연 0.0142퍼센트로)을 듣고 현금을 맡기려는 사람이 창구 앞에 길게 줄을 서 있다.

사람은 많은데 열려 있는 창구는 하나뿐이라 1분에 한 명씩만 응대한다. 욕심 많은 올리버는 줄에 선 사람 중 일부를 골라 그들이 맡기는 현금의 합을 최대로 만들려고 한다. 그 돈은 밤새 은행이 굴린다.

문제가 하나 있다. 어떤 사람은 다른 곳에 가야 해서 영업이 끝날 때까지 기다리지 못한다. 정해진 시각까지 응대를 받지 못하면 그냥 떠난다. 올리버는 홀이 이미 붐빈다는 이유로 출입문의 적외선 센서도 꺼서 새로 들어오는 사람을 막았다.

1분에 최대 한 명씩 응대해서 영업이 끝나기 전에 올리버가 모을 수 있는 현금의 최대 액수를 구하라.

입력

첫 줄에 줄에 선 사람 수 $N$ 과 영업이 끝날 때까지 남은 시간(분) $T$ 가 주어진다 ( $1 \le N \le 10000$ , $1 \le T \le 47$ ).

다음 $N$ 개 줄에는 각각 정수 $c_i$ 와 $t_i$ 가 주어진다. $c_i$ 는 $i$ 번 사람이 가진 현금 액수(스웨덴 크로나)이고, $t_i$ 는 응대를 받지 못하면 $i$ 번 사람이 떠나는 시각으로 지금부터 몇 분 뒤인지를 나타낸다. 한 사람을 응대하는 데 1분이 걸리며, $i$ 번 사람은 늦어도 $t_i$ 분에는 응대를 시작해야 한다. 응대는 $0$ 분, $1$ 분, 그리고 $T-1$ 분까지의 정수 시각 중 하나에 시작하고, 한 시각에는 한 명만 응대한다. $1 \le c_i \le 100000$ 이고 $0 \le t_i < T$ 이다.

출력

영업이 끝나기 전에 줄에 선 사람들에게서 모을 수 있는 현금의 최대 액수를 한 줄에 출력한다.

예제5

예제 1
입력
```
4 4
1000 1
2000 2
500 2
1200 0
```
예상 출력
```
4200
```
예제 2
입력
```
3 4
1000 0
2000 1
500 1
```
예상 출력
```
3000
```
예제 3
입력
```
1 1
100000 0
```
예상 출력
```
100000
```
예제 4
입력
```
5 3
10 0
20 0
30 0
40 0
50 0
```
예상 출력
```
50
```
예제 5
입력
```
5 10
7 0
3 1
9 2
1 3
5 4
```
예상 출력
```
25
```