Gdzie zbudować browar?
Limit pamięci: 32 MB
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 ze standardowego wejścia liczbę miast, odległości między nimi oraz dzienne zapotrzebowania na piwo,
- obliczy minimalny dzienny koszt transportu piwa,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba
całkowita równa liczbie miast,
. W każdym z kolejnych
wierszy zapisana jest para nieujemnych liczb całkowitych oddzielonych
pojedynczym odstępem.
Liczby
zapisane w
-ym wierszu to odpowiednio
zapotrzebowanie na piwo w mieście nr
oraz odległość (w kilometrach)
od miasta nr
do następnego miasta na autostradzie. Kolejne miasta na
autostradzie mają kolejne numery, po mieście nr
leży miasto nr 1.
Całkowita długość autostrady nie przekracza
km.
Zapotrzebowanie na piwo w żadnym mieście nie przekracza
cystern.
Wyjście
Twój program powinien zapisać w pierwszym i jedynym wierszu standardowego wyjścia dokładnie jedną liczbę całkowitą równą minimalnemu dziennemu kosztowi transportu piwa.
Przykład
Dla danych wejściowych:
6 1 2 2 3 1 2 5 2 1 10 2 3
poprawną odpowiedzią jest:
41
Autor zadania: Wojciech Guzicki.