ADAFRIEN - Ada and Friends


Ada the Ladybug has many friends. They always celebrate something and Ada has to buy them gifts. It is pretty costly so she have decided to unfriend some of them. What is the maximum of money she can spare?

Input

The first line of each test-case will contain two integers 1 ≤ Q K ≤ 105, the number of celebrations (Q) and the maximum number of friends Ada wants to unfriend (K).

The next Q lines will contain s (the name of friend to whom Ada will buy gift) and 1 ≤ E ≤ 109+1 (the expenses).

Names will contain at most 40 lowercase english letters.

Output

For each test-case, print the number of money Ada could spare.

Example Input

6 1
uvuvwevwevweonyetenyevweugwemubwemossas 10
ryuk 11
uvuvwevwevweonyetenyevweugwemubwemossas 5
fegla 3
tenshikanade 7
fegla 2

Example Output

15

Example Input

4 3
frodo 1
harrypotter 2
frodo 2
harrypotter 2

Example Output

7

Example Input

7 2
waynebot 7
lhic 4
petr 5
umnik 9
izrak 6
tourist 11
zlobobber 9

Example Output

20

Example Input

6 3
dufresne 5
gump 11
dufresne 3
mcmurphy 19
leon 10
dufresne 1

Example Output

40

hide comments
amulyagaur: 2017-10-20 08:00:30

nice question @Morass

julkas: 2017-10-10 09:53:05

@Morass It works now. 8-)

morass: 2017-10-10 00:26:38

@julkas: Right, thank you, hopefully fixed. Sorry for the inconvenience! :/

julkas: 2017-10-09 21:04:02

@Morass I think at least one test case is not properly formated. Python gives NZEC.


Added by:Morass
Date:2017-10-08
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Tunisian Collegiate Training Contest - Round #01