Baby Seok-hwan, who loves candy, brought a bag containing $N$ candies into his house. There are two types of candies in the bag: small candies weighing 3g and large candies weighing 5g. The clever baby Seok-hwan has calculated the sweetness $s_i$ for every candy in the bag. $s_i$ is a positive integer, and the larger $s_i$ is, the sweeter the candy.

While packing for the shake! 2019 competition, baby Seok-hwan wants to pack as many sweet candies as possible to replenish his sugar levels during the competition. However, the frail baby Seok-hwan can only carry a maximum of $w$g of candy in his bag. What is the maximum possible sum of the sweetness of the candies that baby Seok-hwan can pack while satisfying this condition?

Input

The first line contains the number of candies $N$ and the weight limit $w$. ($1 \le N \le 250\,000, 0 \le w \le 5N$)

The following $N$ lines each contain the type $t_i$ and the sweetness $s_i$ of each candy. ($t_i \in \{3, 5\}, 1 \le s_i \le 10^9$)

Output

Output the maximum sum of sweetness of the candies that baby Seok-hwan can pack while satisfying the condition.

Examples

Input 1

10 11
3 10
3 20
3 30
3 40
3 50
5 20
5 40
5 60
5 80
5 100

Output 1

190

Note

Warning for Java/Kotlin users! Contrary to common knowledge, Java's built-in Arrays.sort function and Kotlin's IntArray.sort() are implemented with an $O(N^2)$ time complexity algorithm. The test data for this problem is designed to cause a time limit exceeded error if those functions are used, so please use other sorting functions such as Collections.sort when solving the problem.