Zadanie

Dedič Dano

Počet bodov: 25, časový limit: 600ms

Dano je zainvestovaný do svojej finančnej budúcnosti. Jeho zainvestovanosť zašla až tak ďaleko, že sa rozhodol zistiť čo všetko zdedí. Čoskoro ale pochopil, že dedenie nie je len sranda a okrem toho, že dedičské konanie nie je lacný špás, mohol by zdediť aj dlhy.

Preto zisťuje, aké dlžoby by zdedil od ktorého rodinného člena, aby sa poprípade vhodne vydedil. To ale nie je len tak.

Ak by sa vydedil od príliš veľa rodinných členov, vydedila by ho celá rodina a nezdedil by ani mäkké f a už vôbec nie strýkovo bohatstvo a ranč v Kalifornii. Teraz chce zistiť, od akého veľkého dlhu sa vie odbremeniť bez toho, aby o toto bohatstvo prišiel.

Vstup a výstup

Na vstupe sú dve celé čísla \(n\) a \(k\) \(( 1\leq n, k \leq 10^5 )\) počet dlhov, ktoré Dano zdedí a počet príbuzných, od ktorých sa môže vydediť. Nasledujúcich \(n\) riadkov obsahuje reťazec \(m_i\) \(( 1\leq |m_i| \leq 40)\) – meno príbuzného, zložené iba z malých písmen anglickej abecedy a celé číslo \(d_i\) \(( 1\leq d_i \leq 10^6 )\) jeden z dlhov, ktorý od neho zdedí. Na výstup vypíšte jedno celé číslo – najväčší možný dlh, ktorého sa Dano môže zbaviť, ak sa vydedí od najviac \(k\) rôznych príbuzných.

Príklad

Input:

6 1
amvhegiiugvajoqerhgvsduamioaghaiodjgiua 11
pkrs 12
amvhegiiugvajoqerhgvsduamioaghaiodjgiua 6
anefm 7
panigfkiog 16
anefm 4

Output:

17

Input:

4 3
andrej 3
dano 1
andrej 5
dano 2

Output:

11

Hoc by sa Dano mohol zbaviť aj viacerých príbuzných, nemá už koho.

Input:

7 2
pantograf 7
zehlicka 4
sergej 5
mravec 9
bageta 6
laminatka 11
hercules 9

Output:

20
Pre odovzdávanie sa musíš prihlásiť.