Bajtocka masakra piłą mechaniczną

Wzdłuż głównej rzeki Bajtocji, która oczywiście płynie ze szczytu góry w dół, rośnie n drzew. Drzewa owe zasłaniały widok królowi, więc wbrew protestom ekologów postanowił je ściąć. Żeby drewno się nie zmarnowało, każde drzewo po ścięciu trzeba dostarczyć do tartaku.

Drzewa mogą być spławiane tylko w dół rzeki. Przy ujściu znajduje się już jeden działający tartak, ale król postanowił przy okazji zbudować dwa kolejne.

Tobie przypadła ważna rola wybrania miejsca budowy nowych tartaków, tak aby koszt transportu drewna był jak najmniejszy. Transport jednej tony drewna na odległość kilometra kosztuje jeden grosz.

Zadanie

Napisz program, który:

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna n - liczba drzew (2 ≤ n ≤ 20000). Drzewa są ponumerowane 1,2,...,n, zaczynając od źródła rzeki w kierunku ujścia. Każdy z kolejnych n wierszy zawiera dwie dodatnie liczby całkowite oddzielone pojedynczym odstępem. Wiersz i+1-szy zawiera: wi - wagę (w tonach) i-tego drzewa i di - odległość (w kilometrach) pomiędzy drzewami i i i+1, 1 ≤ wi ≤ 10000, 0 ≤ di ≤ 10000. Ostatnia z tych liczb, dn, jest odległością od drzewa numer n do ujścia rzeki. Wiadomo, że koszt transportu całego drewna do tartaku przy ujściu nie przekroczy 2*109 groszy.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę naturalną: minimalny koszt transportu drewna do tartaków.

Przykład

Dla danych wejściowych:
9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1
poprawnym wynikiem jest: 
26

Zadanie pochodzi z CEOI 2004