Hide

Problem A
Pizzubestun

Languages en is
/problems/pizzubestun/file/statement/is/img-0001.png
Mahjong pizza
Nonni á æfmæli, og honum langar að panta uppáhalds matinn sinn fyrir alla í veislunni, pizzur. Uppáhalds pizzastaðurinn hans, Mahjong, er með svokallað “Tvennutilboð”, þar sem hægt er að panta 2 stórar pizzur af matseðli, en einungis er borgað fyrir dýrari pizzuna.

Nonni er búinn að spyrja gestina hvernig pizzur þau myndu vilja, þannig hann veit hversu margar pizzur þarf að panta og hvaða pizzur þarf að panta.

Nonna langar að eyða sem minnst í pizzurnar, og biður þig um aðstoð, gefið er pizzurnar sem hann vill panta, og verðið fyrir hverja pizzu—þú þarft að finna út hvaða pizzur væri best að para saman í tvennutilboð til að lágmarka kostnaðinn (það er líka hægt að panta pizzur sem stakar pizzur).

Inntak

Fyrsta línan inniheldur töluna $n$, fjölda pizza sem þarf að panta. Næstu $n$ línur innihalda nafn á pizzu og verð, aðskilið með bili. Nafnið á hverri pizzu inniheldur einungis ASCII stafi (og enga tölustafi). Verðið fyrir hverja pizzu er alltaf jákvæð heiltala og minni en $10^9$.

Úttak

Skrifið út ódýrasta mögulega verðið á þessari pöntun.

Stigagjöf

Hópur

Stig

Takmarkanir

1

50

$1 \leq n \leq 1000$

2

50

$1 \leq n \leq 10^5$

Sample Input 1 Sample Output 1
4
Prinsinn 2499
Piparinn 2399
Margherita 1899
Pepparinn 2099
4598
Sample Input 2 Sample Output 2
3
Guffi 3099
BaraDodlur 2899
Margherita 1899
4998