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.