Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×
I. Record Compression
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
commatose
Glass Beach, Plastic Death

Amber wants to store her favorite songs on a vinyl record!

Amber's record can store $$$m$$$ bytes of data (it's a fancy digital record), and Amber has $$$n$$$ songs which she wants to store. Each of the $$$n$$$ songs has a title $$$s_i$$$, and it takes $$$|s_i|$$$ bytes to store the $$$i^\text{th}$$$ song. Additionally, Amber values different songs differently, so she assigns a value $$$v_i$$$ to the $$$i^\text{th}$$$ song. Moreover, Amber does not mind listening to the same song multiple times; that is, she may store the same song multiple times on her vinyl, and each time she stores the $$$i^\text{th}$$$ song, it will add the value $$$v_i$$$ to the total value of the record.

Amber would like to maximize the total value of the songs she stores on her digital vinyl. Given the size of her vinyl (in bytes), as well as the titles and values of each of her favorite songs, please help Amber figure out the maximum total value she can achieve by storing the optimal songs!

Input

The first line of input will contain two space-separated integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$) — the number of favorite songs Amber has and the size of her vinyl record in bytes.

The next $$$n$$$ lines will each describe one of Amber's favorite songs. The $$$i^\text{th}$$$ of these lines will contain a string $$$s_i$$$ ($$$1 \leq |s_i| \leq 2 \cdot 10^5$$$) consisting of lower and uppercase English letters, followed by a space, followed by an integer $$$v_i$$$ ($$$1 \leq v_i \leq 10^9$$$). It is guaranteed that $$$\sum_{i=1}^n |s_i| \leq 2 \cdot 10^5$$$.

Output

The output should consist of a single integer, the maximum total value that Amber can achieve by optimally storing her favorite songs on her vinyl record.

Examples
Input
3 7
Creep 1
HotelCalifornia 2
One 3
Output
6
Input
5 30
BohemianRhapsody 20
HeyJude 12
DancingQueen 19
PurpleHaze 23
commatose 52
Output
156
Note

In the first sample test case, Amber could store the song "One" twice using up six bytes of memory and earning a total value of six as well.

In the second sample test case, it is optimal for Amber to store the song "commatose" three times using up 27 bytes of memory, for a total value of $$$52 \cdot 3 = 156$$$.