은행 대기열

Oliver는 KTH 근처에 있는 은행의 지점장이며 곧 문을 닫고 싶어 한다. 은행이 이자율을 $42\%$만큼(연 $0.01\%$에서 연 $0.0142\%$로) 올렸다는 소식을 듣고 현금을 계좌에 입금하려는 많은 사람이 대기열에 서 있다.

하지만 사람이 너무 많고 창구는 하나만 열려 있으며, 이 창구에서는 분당 한 사람만 응대할 수 있다. 욕심 많은 Oliver는 이 사람들이 예치하는 현금의 총액을 가능한 한 크게 하여 그 돈이 밤새 은행을 위해 일하게 할 수 있도록 대기열에서 일부 사람을 선택하고 싶어 한다.

하지만 문제가 있다. 어떤 사람들은 다른 곳으로 가야 하므로 은행이 문을 닫을 때까지 기다릴 시간이 없으며, 특정 시각 전에 응대를 받아야 하고 그 시각이 지나면 그냥 떠난다. 또한 이미 홀이 너무 붐비기 때문에 더는 아무도 들어올 수 없도록 Oliver는 은행 밖의 적외선 문 센서를 껐다.

과제

Oliver가 분당 최대 한 사람을 응대하여 은행이 문을 닫기 전에 현재 대기열에 서 있는 사람들에게서 받을 수 있는 현금이 얼마인지 계산하도록 도와주자.

입력의 첫째 줄에는 대기열에 있는 사람의 수와 Oliver가 은행을 닫을 때까지 남은 시간을 분 단위로 나타내는 두 정수 $N$ $(1\leq N\leq 10\,000)$와 $T$ $(1\le T \le 47)$가 주어진다. 이어서 $N$개의 줄이 주어지며, 각 줄에는 2개의 정수 $c_i$와 $t_i$가 주어진다. 이는 사람 $i$이 가진 현금의 액수를 스웨덴 크로나 단위로 나타낸 값과, 지금부터 몇 분 후까지 응대받지 못하면 사람 $i$이 떠나는지를 각각 나타낸다. 한 사람을 응대하는 데 일 분이 걸리며, 늦어도 시각 $t_i$에는 그 사람의 응대를 시작해야 한다는 점에 유의하라. $1\le c_i \le 100\,000$이고 $0 \le t_i < T$이라고 가정해도 된다.

은행이 문을 닫기 전에 대기열에 있는 사람들에게서 받을 수 있는 돈의 최대 액수를 한 줄에 출력한다.