Droga do Bajtogóry [B]

Limit pamięci: 32 MB

Bajtazar wstał wczesnym rankiem, tuż po świcie. Planuje dziś zdobyć szczyt Bajtogóry, dlatego noc spędzał w schronisku położonym w samym centrum malowniczego pasma Bajtydu Niskiego. Bajtogóra jest najwyższą górą całego pasma, w związku z czym na każdym skrzyżowaniu szlaków znajduje się tabliczka, która wskazuje na szlak prowadzący w kierunku szczytu.

Wychodząc ze schroniska, Bajtazar spotkał przewodnika, który zna Bajtyd Niski jak własną kieszeń. Przewodnik ostrzegł Bajtazara, że oznakowanie szlaków jest w trakcie reorganizacji, dlatego na tabliczkach na skrzyżowaniach szlaków nie należy polegać. W szczególności na samym szczycie Bajtogóry także znajduje się tabliczka wskazująca pewien szlak jako prowadzący na Bajtogórę!

Przewodnik zamierza wyjaśnić Bajtazarowi, jak trafić na szczyt. Szczęśliwie, wszystkie skrzyżowania szlaków są ponumerowane od do , a na każdym skrzyżowaniu jest tabliczka z jego numerem. Instrukcja przewodnika będzie miała następującą postać: "Idź zgodnie z drogowskazami, aż dotrzesz do skrzyżowania numer , tam wyciągnij mapę i wejdź na szlak, który łączy skrzyżowanie ze skrzyżowaniem . Idź dalej zgodnie z drogowskazami, aż dotrzesz do skrzyżowania numer . Tam spójrz na mapę i wejdź na szlak, który łączy i ... Na koniec po dotarciu do spójrz po raz ostatni na mapę i wejdź na szlak, który łączy z . Idąc dalej zgodnie z drogowskazami, dotrzesz na szczyt Bajtogóry".

Bajtazar nie chce, by opis trasy na szczyt był skomplikowany, dlatego poprosił przewodnika, by ten polecił mu taką trasę, podczas której będzie musiał spoglądać na mapę co najwyżej razy.

Przewodnik myślał dłuższą chwilę nad tym, jak pokierować Bajtazara, bo wie, że niektóre szlaki są ciekawsze od innych, i chciałby poprowadzić go jak najbardziej interesującą trasą.

Trasa może przebiegać wielokrotnie po tych samych szlakach i skrzyżowaniach (niektóre szlaki są tak ciekawe, że warto zobaczyć je kilka razy!).

Bajtazar stwierdza, że doszedł do celu, gdy po wykonaniu wszystkich instrukcji przewodnika po raz pierwszy znajdzie się na szczycie. W trakcie wykonywania instrukcji przewodnika Bajtazar może wielokrotnie przechodzić przez szczyt, lecz zatrzyma się na Bajtogórze dopiero po wykonaniu wszystkich instrukcji.

Na ile ciekawa będzie trasa, którą przewodnik zaproponuje Bajtazarowi?

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem. Oznaczają one liczbę skrzyżowań szlaków oraz maksymalną liczbę razy, jaką Bajtazar chce spoglądać na mapę. Skrzyżowania są ponumerowane od do , schronisko znajduje się przy skrzyżowaniu numer , zaś szczyt Bajtogóry to skrzyżowanie numer .

W kolejnych wierszach znajdują się opisy kolejnych skrzyżowań szlaków. Opis każdego skrzyżowania zawarty jest w jednym wierszu i składa się z liczb całkowitych pooddzielanych pojedynczymi odstępami. Pierwsza liczba opisu, (), oznacza liczbę szlaków wychodzących z tego skrzyżowania. Po niej następuje par liczb , (, ), które oznaczają, że z -tego skrzyżowania można pójść do skrzyżowania numer po szlaku, którego współczynnik ciekawości wynosi . Pierwsza para liczb oznacza szlak, który według tabliczki na skrzyżowaniu prowadzi do Bajtogóry. Każdy szlak jest dwukierunkowy i łączy dwa różne skrzyżowania. Dwa skrzyżowania mogą być połączone co najwyżej jednym szlakiem. Łączna liczba wszystkich szlaków nie przekracza .

Każdy szlak łączący skrzyżowania o numerach oraz będzie wymieniony dwukrotnie: raz na liście szlaków wychodzących ze skrzyżowania , drugi raz na liście szlaków wychodzących ze skrzyżowania . W obydwóch przypadkach podany współczynnik ciekawości będzie taki sam.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia wypisz jedną liczbę całkowitą, oznaczającą największą możliwą sumę współczynników ciekawości kolejnych szlaków na trasie ze schroniska na szczyt Bajtogóry spełniającej wymagania Bajtazara. Możesz założyć, że istnieje co najmniej jedna taka trasa.

Przykład

Dla danych wejściowych:

5 2
2 3 4 2 2
3 1 2 5 4 4 3
2 1 4 4 3
3 2 3 5 5 3 3
2 2 4 4 5

poprawną odpowiedzią jest:

14

Wyjaśnienie do przykładu. Na powyższym rysunku krawędzie reprezentują szlaki łączące poszczególne skrzyżowania, liczby przy krawędziach - współczynniki ciekawości, a strzałki oznaczają szlaki wskazywane przez tabliczki na poszczególnych skrzyżowaniach.

Przewodnik nakaże Bajtazarowi dwukrotne spojrzenie na mapę, kolejno na skrzyżowaniach numer 3 i 2. W ten sposób wędrówka Bajtazara może prowadzić po trasie . Sumaryczna ciekawość przebytych szlaków to 14.

Autor zadania: Mirosław Michalski.