Problem E
Línuhlýnun

Mynd fengin af flickr.com

Íbúar Línulands fengu þær fréttir nýlega að byggja ætti háskóla í landinu. Þetta eru þau himinlifandi með, enda á að kenna Línulega algebru, Línulega bestun og Línulega fallagreiningu í skólanum, svo eitthvað sé nefnt.

Gróðurhúsaáhrif hafa farið illa með Línuland eins og önnur lönd, og hefur þetta valdið mikilli Línuhlýnun. Yfirvöld hafa áhyggjur af því að þetta gæti versnað þegar nemendur nýja háskólans fara að keyra í skólann, enda gæti það aukið koltvíoxíðmengun. Þau hafa því fengið þig til að aðstoða við að velja staðsetningu skólans til að lágmarka mengun.

Eins og nafnið gefur til að kynna þá býr fólkið í Línulandi á línu. Húsnúmer í landinu eru jákvæðar heiltölur, en fjarlægð á milli húsa númer $a$ og $b$ er $|a-b|$ kílómetrar.

Gefinn listi af nemendum háskólans, hvar þeir eiga heima, og hversu mikið af koltvíoxíð bíllinn þeirra myndar á hverjum kílómetra, finndu í hvaða húsnúmeri væri best að byggja háskólann til lágmarka heildarkoltvíoxíðmengun á hverjum morgni þegar nemendur keyra í skólann.

Athugið að margir nemendur gætu búið í sama húsnúmeri. Það er í lagi að byggja háskólann í húsi þar sem nemendur eiga þegar heima, en þá fá þeir einfaldlega að búa í háskólanum. (Vá, heppnir þeir!)

Inntak

Fyrsta línan í inntakinu inniheldur eina heiltölu $n$ ($1 \leq n \leq 2\cdot 10^5$), fjöldi nemenda í nýja háskólanum.

Síðan koma $n$ línur, ein fyrir hvern nemenda, þar sem lína $i$ inniheldur tvær heiltölur $x_i$ ($1 \leq x_i \leq 10^9$), númer hússins sem nemandi $i$ býr í, og $c_i$ ($1 \leq c_i \leq 10^3$), magn koltvíoxíðs sem bíll nemanda $i$ mengar á hverjum kílómetra.

Úttak

Skrifið út í hvaða húsnúmeri væri best að byggja háskólann til að lágmarka heildarkoltvíoxíðmengun á hverjum morgni þegar nemendur keyra í skólann. Ef mörg húsnúmer koma til greina, skrifið út minnsta húsnúmerið sem kemur til greina.

Stigagjöf

3
1 1
2 1
5 1

2

3
1 1
2 1
5 3

5

4
9 2
4 1
18 4
4 2

9