Her boyfriend left her. The Plastics left her. Now, Regina George just wants to watch the world burn.

Her weapon? The Burn Book — a book of insults and roasts. Each page targets one person from school and comes with a "burn value" ~b~. Regina can select at most ~k~ pages to copy and post all over the school.

Being burned sucks. Being burned multiple times sucks more. For any person, the total pain they suffer is calculated as:

$$\displaystyle (\text{sum of burn values about them}) \times (\text{number of pages about them})$$

For example, if Regina posts ~3~ pages about Janis with burn values ~3~, ~2~, and ~10~, Janis suffers ~(3 + 2 + 10) \times 3 = 15 \times 3 = 45~ pain.

Given all the pages Regina has, and the limit ~k~ on how many she can choose, what's the maximum total pain she can inflict?

Input

The first line consists of an integer ~n~ ~(1 \leq n \leq 10^5)~, the number of pages Regina has at her disposal.

The next line consists of an integer ~k~ ~(1 \leq k \leq 10^5)~, the number of pages Regina can choose to disperse in the halls.

The next ~n~ lines consist of ~S~ and ~b~, where ~S~ ~(1 \leq S.\text{length} \leq 10)~ is person being insulted, and ~b~ ~(1 \leq b \leq 10^8)~ is the insult's burn value. ~S~ can be any string of English characters.

Output

Output the total amount of pain that Regina can inflict onto her peers.

Example

Input

7
4
Janis 2
Janis 5
Janis 4
Trang 2
Trang 1
Regina 15
Damien 6

Output

48

Regina can release all ~3~ pages about Janis, which inflicts ~(2 + 5 + 4) = 11 \times 3 = 11 \times 3 = 33~ pain overall. She can then release the ~1~ page about herself, which inflicts ~15 \times 1 = 15~ pain. Overall, she has inflicted ~33 + 15 = 48~ pain, which is the maximum in this case.