Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Selling Souvenirs

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAfter several latest reforms many tourists are planning to visit Berland, and Berland people understood that it's an opportunity to earn money and changed their jobs to attract tourists. Petya, for example, left the IT corporation he had been working for and started to sell souvenirs at the market.

This morning, as usual, Petya will come to the market. Petya has *n* different souvenirs to sell; *i*th souvenir is characterised by its weight *w*_{i} and cost *c*_{i}. Petya knows that he might not be able to carry all the souvenirs to the market. So Petya wants to choose a subset of souvenirs such that its total weight is not greater than *m*, and total cost is maximum possible.

Help Petya to determine maximum possible total cost.

Input

The first line contains two integers *n* and *m* (1 ≤ *n* ≤ 100000, 1 ≤ *m* ≤ 300000) — the number of Petya's souvenirs and total weight that he can carry to the market.

Then *n* lines follow. *i*th line contains two integers *w*_{i} and *c*_{i} (1 ≤ *w*_{i} ≤ 3, 1 ≤ *c*_{i} ≤ 10^{9}) — the weight and the cost of *i*th souvenir.

Output

Print one number — maximum possible total cost of souvenirs that Petya can carry to the market.

Examples

Input

1 1

2 1

Output

0

Input

2 2

1 3

2 2

Output

3

Input

4 3

3 10

2 7

2 8

1 1

Output

10

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/26/2018 16:44:23 (f2).

Desktop version, switch to mobile version.

User lists

Name |
---|