Przemytnicy
Limit pamięci: 32 MB
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 w metal
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 , że:
-
to złoto,
-
dla każdego alchemicy potrafią
otrzymać metal z metalu , 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 ,
dla ) 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 oznaczająca
liczbę rodzajów metali, .
W wierszu o numerze , dla ,
znajduje się nieujemna parzysta liczba całkowita -
cena 1 kg metalu oznaczonego numerem , .
Przyjmujemy, że złoto ma numer 1.
W wierszu o numerze znajduje się jedna nieujemna liczba całkowita
równa liczbie procesów przemiany znanych alchemikom, .
W każdym z kolejnych wierszy znajdują się po trzy
liczby naturalne, pooddzielane pojedynczymi odstępami,
opisujące kolejne procesy przemiany.
Trójka liczb oznacza, że alchemicy potrafią
z metalu o numerze otrzymywać metal o numerze i
za zamianę 1 kg surowca każą sobie płacić bajtalarów,
.
Uporządkowana para liczb i 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
poprawną odpowiedzią jest:
60
Autor zadania: Łukasz Kowalik.