Wstęp do programowania w C++

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 jeszcze nie wie, w którym mieście wybuduje browar, ale jak już będzie to wiedział, to 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,
• wczyta liczbę zapytań
• każde zapytanie określać będzie numer miasta, w którym inwestor chce zbudować browar
• dla każdego zapytania obliczy minimalny dzienny koszt transportu piwa,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę miast (4 < n < 1000007).

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 10⁹ km. Zapotrzebowanie na piwo w żadnym mieście nie przekracza  cystern. Następnie jedna liczba q nie większa niż 10⁶ określająca liczbę zapytań. Każde zapytanie składa się z jednej liczby całkowitej będącej numerem miasta, w którym inwestor chce wybudować browar.

Wyjście

Twój program powinien wypisać dla każdego zapytania  dokładnie jedną liczbę całkowitą równą minimalnemu dziennemu kosztowi transportu piwa do danego miasta.

Przykład
Dla danych wejściowych:
6
1 2
2 3
1 2
5 2
1 10
2 3
1
3

poprawną odpowiedzią jest:
41