Problem G
Lieutenant Slotto

Lieutenant Slotto is currently garrisoning $N$ castles. Each castle contains riches worth $l_i$ gold coins and is defended by $g_i$ soldiers.

You plan to attack Slotto’s castles and have a total of $T$ soldiers at your disposal. Each soldier can be sent to attack exactly one castle. If you attack castle $i$ with at least $g_i$ soldiers, the attack succeeds and you can plunder its riches. If you send fewer soldiers, the attack fails.

If you distribute your soldiers optimally, how many gold coins’ worth of riches can you obtain?

Input

The first line of input contains the integers $N$ and $T$ ($1 \leq N \leq 2 \cdot 10^5$, $1 \leq T \leq 10^6$), the number of castles and the number of soldiers you have.

The following $N$ lines each describe a castle. Each of these lines contains the integers $l_i$ and $g_i$ ($1 \leq l_i \leq 5$, $1 \leq g_i \leq 10^6$), the value of the riches in castle $i$ and the number of guards defending castle $i$.

Output

Print a single integer: the maximum total amount of riches you can seize if you distribute your soldiers optimally.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of samples

In sample $1$, an optimal solution is to send $5$ troops to castle $2$ (the one with $l_i = g_i = 4$) and $2$ troops to castle $4$ (the one with $l_i = g_i = 2$), yielding a total of $6$ gold coins’ worth of riches.

In sample $2$, an optimal solution is to send all troops to castle $1$.

In both cases, there are other allocations that give the same amount of riches.

5 7
5 6
4 4
3 5
2 2
1 3

6

3 10
5 9
3 6
3 6

5