Bajtocja słynie z bogatych złóż złota, dlatego przez długie lata kwitła sprzedaż tego kruszcu do sąsiedniego królestwa, Bitlandii. Niestety powiększająca się ostatnio dziura budżetowa zmusiła króla Bitlandii do wprowadzenia zaporowych ceł na metale i minerały. Handlarze przekraczający granicę muszą zapłacić 50% wartości przewożonego ładunku. Bajtockim kupcom grozi bankructwo. Na szczęście bajtoccy alchemicy opracowali sposoby pozwalające zamieniać pewne metale w inne. Pomysł kupców polega na tym, aby z pomocą alchemików zamieniać złoto w pewien tani metal, a następnie, po przewiezieniu go przez granicę i zapłaceniu niewielkiego cła, znowu otrzymywać z niego złoto. Niestety alchemicy nie znaleźli sposobu na zamianę dowolnego metalu w dowolny inny. Może się więc zdarzyć, że proces otrzymania danego metalu ze złota musi przebiegać wielostopniowo i że na każdym etapie uzyskiwany będzie inny metal. Alchemicy każą sobie słono płacić za swoje usługi i dla każdego znanego sobie procesu zamiany metalu A w metal B wyznaczyli cenę za przemianę 1 kg surowca. Handlarze zastanawiają się, w jakiej postaci należy przewozić złoto przez granicę, oraz jaki ciąg procesów alchemicznych należy zastosować, aby zyski były możliwie największe.

Zadanie

Pomóż uzdrowić bajtocką gospodarkę! Napisz program, który:

• Wczyta tabelę cen wszystkich metali, a także ceny przemian oferowanych przez alchemików.
• Wyznaczy taki ciąg metali m₀, m₁, ..., m_k, że:
  • m₀ = m_k to złoto,
  • dla każdego i=1, 2, ..., k alchemicy potrafią otrzymać metal m_i z metalu m_i-1 oraz
  • koszt wykonania całego ciągu procesów alchemicznych dla 1 kg złota, powiększony o płacone na granicy cło (50% ceny 1 kg najtańszego z metali m_i, dla i = 0, 1, ..., k) jest najmniejszy z możliwych.
  Zakładamy, że podczas procesów alchemicznych waga metali nie zmienia się.
• Wypisze koszt wykonania wyznaczonego ciągu procesów alchemicznych powiększony o płacone na granicy cło.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna dodatnia liczba całkowita n oznaczająca liczbę rodzajów metali, 1 <= n <= 5000. W wierszu o numerze k+1, dla 1 <= k <= n, znajduje się nieujemna parzysta liczba całkowita p_k - cena 1 kg metalu oznaczonego numerem k, 0 <= p_k <= 10⁹. Przyjmujemy, że złoto ma numer 1. W wierszu o numerze n+2 znajduje się jedna nieujemna liczba całkowita m równa liczbie procesów przemiany znanych alchemikom, 0 <= m <= 100000. W każdym z kolejnych m wierszy znajdują się po trzy liczby naturalne, pooddzielane pojedynczymi odstępami, opisujące kolejne procesy przemiany. Trójka liczb a, b, c oznacza, że alchemicy potrafią z metalu o numerze a otrzymywać metal o numerze b i za zamianę 1 kg surowca każą sobie płacić c bajtalarów, 1 <= a,b <= n, 0 <= c <= 10000. Uporządkowana para liczb a i b może się pojawić w danych co najwyżej jeden raz.

Wyjście

Twój program powinien pisać na standardowe wyjście. W pierwszym wierszu powinna zostać wypisana jedna liczba całkowita - koszt wykonania wyznaczonego ciągu procesów alchemicznych powiększony o płacone na granicy cło.

Przykład

Dla danych wejściowych:

4
200
100
40
2
6
1 2 10
1 3 5
2 1 25
3 2 10
3 4 5
4 1 50

poprawnym wynikiem jest:

60