Problem E
Pizzubestun
Languages
en
is
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 |
