VII Olimpiada Informatyczna 1999/2000
|
Zadanie: BRO
|
Autor: Wojciech Guzicki
|
Zawody I stopnia |
Plik źródłowy: | BRO.??? (np. pas, c, cpp) |
Plik wykonywalny: | BRO.exe |
Plik wejściowy: | BRO.in |
Plik wyjściowy: | BRO.out |
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.
Napisz program, który:
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 zi di 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.
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.
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