Mieszkańcy bajtockiej wyspy Abstynencja bardzo lubią piwo bezalkoholowe. Do tej pory piwo bezalkoholowe sprowadzano z Polski, ale w tym roku w jednym z miast na Abstynencji zostanie wybudowany browar. Wszystkie miasta wyspy leżą na wybrzeżu i są połączone autostradą obiegającą wyspę wzdłuż brzegu. Inwestor budujący browar zebrał informacje o zapotrzebowaniu na piwo, tj. ile cystern piwa trzeba codziennie dostarczyć do każdego z miast. Dysponuje także zestawieniem odległości pomiędzy miastami. Koszt transportu jednej cysterny na odległość 1 km wynosi 1 talar. Dzienny koszt transportu to suma, jaką trzeba wyłożyć, by do każdego miasta przetransportować z browaru tyle cystern, ile wynosi zapotrzebowanie w danym mieście. Jego wielkość zależy od miejsca położenia browaru. Inwestor chce zminimalizować koszty transportu piwa.

Zadanie

Napisz program, który:

• wczyta z pliku tekstowego BRO.IN liczbę miast, odległości między nimi oraz dzienne zapotrzebowania na piwo,
• obliczy minimalny dzienny koszt transportu piwa,
• zapisze wynik w pliku tekstowym BRO.OUT.

Wejście

W pierwszym wierszu pliku tekstowego BRO.IN jest zapisana jedna liczba całkowita n równa liczbie miast, 5 <= n <= 10 000. W każdym z kolejnych n wierszy zapisana jest para nieujemnych liczb całkowitych oddzielonych pojedynczym odstępem. Liczby zⁱ dⁱ zapisane w (i+1)-ym wierszu to odpowiednio zapotrzebowanie na piwo w mieście nr i oraz odległość (w kilometrach) od miasta nr i do następnego miasta na autostradzie. Kolejne miasta na autostradzie mają kolejne numery, po mieście nr n leży miasto nr 1. Całkowita długość autostrady nie przekracza 1 000 000 km. Zapotrzebowanie na piwo w żadnym mieście nie przekracza 1 000 cystern.

Wyjście

Twój program powinien zapisać w pierwszym i jedynym wierszu pliku tekstowego BRO.OUT dokładnie jedną liczbę całkowitą równą minimalnemu dziennemu kosztowi transportu piwa.

Przykład

Dla pliku wejściowego BRO.IN:

6
1 2
2 3
1 2
5 2
1 10
2 3

poprawną odpowiedzią jest plik wyjściowy BRO.OUT:

41