Problem A
Pizzubestun

Mahjong pizza

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

4
Prinsinn 2499
Piparinn 2399
Margherita 1899
Pepparinn 2099

4598

3
Guffi 3099
BaraDodlur 2899
Margherita 1899

4998