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.
-
- 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.