Bank Queue

Interview

Time limit1sMemory limit256 MB

Summary

Pick at most one person per minute before each deadline to maximize the total cash collected.

Level: Medium5 of 10
Topics: Greedy, Heap, Sorting
Solved: No attempts yet

Problem

Oliver manages a bank and wants to close for the day soon. A long queue has formed at the counter: people heard that the bank raised its interest rate by 42 percent (from 0.01 percent per year to 0.0142 percent per year) and they all want to deposit cash.

There are far more people than time. Only one counter is open and it serves one person per minute. Oliver is greedy, so he wants to pick a subset of the queue whose total deposited cash is as large as possible. That money then works for the bank overnight.

There is a catch. Some people have to be somewhere else and cannot wait until the bank closes, so if they are not served by a certain time they simply leave. Oliver also switched off the infrared door sensor so that nobody else can come in, because the hall is crowded already.

Compute the largest amount of cash Oliver can collect before the bank closes, serving at most one person per minute.

Input

The first line contains the number of people in the queue $N$ and the time in minutes until the bank closes $T$ ( $1 \le N \le 10000$ , $1 \le T \le 47$ ).

Each of the next $N$ lines contains two integers $c_i$ and $t_i$ . Here $c_i$ is the amount of cash in Swedish crowns that person $i$ carries, and $t_i$ is the time in minutes from now after which person $i$ leaves if not served. Serving one person takes one minute, and person $i$ must be started no later than minute $t_i$ . A service starts at an integer minute among $0$ , $1$ , up to $T-1$ , and only one person is served at each of those minutes. The values satisfy $1 \le c_i \le 100000$ and $0 \le t_i < T$ .

Output

Print one line with the largest amount of money that can be collected from the queue before the bank closes.

Examples5

Example 1
Input
```
4 4
1000 1
2000 2
500 2
1200 0
```
Expected output
```
4200
```
Example 2
Input
```
3 4
1000 0
2000 1
500 1
```
Expected output
```
3000
```
Example 3
Input
```
1 1
100000 0
```
Expected output
```
100000
```
Example 4
Input
```
5 3
10 0
20 0
30 0
40 0
50 0
```
Expected output
```
50
```
Example 5
Input
```
5 10
7 0
3 1
9 2
1 3
5 4
```
Expected output
```
25
```