Zadanie

Hravé radule

Počet bodov: 50

V dnešných časoch trávime doma výrazne viac času ako obyčajne. A samozrejme ho väčšina ľudí trávi veľmi neproduktívne. Jožko napríklad namiesto programovania sleduje závody slimákov. Dokonca si trénuje vlastný závodný tím. Má doma zostrojenú pretekársku dráhu zloženú z dvoch rovných úzkych tratí. V jednej idú slimáky jedným smerom, v druhej zasa opačným. Ešte ich nezvládol vycvičiť aby prechádzali z jednej trate do druhej takže ich musí vždy preložiť sám.

Jožko tréning berie vážne a teda o každom slimákovi v jeho stajniach vie všetko, aj to, koľko sekúnd mu trvá prejsť z jedného konca trate na druhý. O každom slimákovi zistil, koľko kôl (teda prejední dvoch dĺžok trate) denne potrebuje prejsť aby bol jeho tréning optimálny. Teraz už iba potrebuje vedieť, koľko času mu tréning jeho slimákov každý deň zaberie.

Na začiatku tréningu Jožko umiestni slimáky do radu na jednu trať (poradie si môže zvoliť). Následne sa všetky slimáky naraz rozbehnú tým istým smerom. Keďže trať je úzka, slimáky sa nemôžu predbiehať a teda ak ide nejaký slimák za pomalším, môže cestovať nanajvýš rýchlosťou toho pomalšieho. Keď slimáky prídu na koniec trate, Jožko ich manuálne presunie do druhej trate, môže ich pri tom ľubovoľne preusporiadať. Ak na koniec trate príde kolóna slimákov, uvažujeme že všetci prišli naraz a že ich naraz všetkých premiestni do druhej trate. Uvažujeme že slimáky sú veľmi malé, nemôžu sa na trati otáčať a vždy cestujú najrýchlejšie ako môžu.

Ak Jožko bude slimáky usporiadavať optimálne, ako dlho potrvá kým všetky splnia svoj denný tréning?

Formát vstupu

Na vstupe bude viacero úloh. Každá úloha sa začína riadkom s jedným číslom \(N\), počtom slimákov. Nasleduje \(N\) riadkov, na \(i\)-tom z nich dve čísla, \(C\) a \(K\) - čas potrebný na prekonanie jednej dĺžky trate a počet kôl v dennom tréningu \(i\)-teho slimáka. Vstup je ukončený úlohou s \(N=0\).

Formát výstupu

Na výstup vypíšte toľko riadkov, koľko je na vstupe úloh. Na každom jedno celé číslo - odpoveď pre danú úlohu.

Obmedzenia

Vstupy sú rozdelené do niekoľko sád, obtiažnosť sád sa stupňuje. V najťažšej sade pre každú úlohu platí \(1 \leq N \leq 100\), \(1 \leq max(C_i) \leq 500\), \(1 \leq max(K_i) \leq 10^4\) a \(sum(K_i) \leq 5*10^6\).

Príklad

Input:

2 
10 240 
15 160 
2 
10 30 
15 20 
4 
2 4 
7 2 
8 2 
18 1 
3 
2 6 
7 2 
8 2 
4
2 6
3 4
4 3
6 2
0

Output:

4800
600
40
36
24