Żaglówka
Limit pamięci: 32 MB
Nie tak dawno temu Kubuś Puchatek wybrał się z Tygryskiem popływać żaglówką.
Tygrysek jest już doświadczonym żeglarzem i steruje łódką. Kubuś zaś jest szczurem lądowym,
który trochę się boi. Za każdym razem, gdy zmienia się kierunek płynięcia żaglówki, zmienia
się też kąt przechyłu żaglówki pod wpływem siły wiatru. Każda taka zmiana powoduje
głośne wykrzyknięcie Kubusia: "czy to normalne, że są takie przechyły?". Wiadomo,
im większa zmiana wychylenia łódki, tym głośniej Kubuś krzyczy, ale także ma więcej wrażeń z wakacji.
Łączne wrażenia Kubusia z rejsu to suma kwadratów wszystkich zmian kątów wychylenia
przy kolejnych zwrotach. Pomóż Tygryskowi je zmaksymalizować.
Rejs zaczyna się w Pięknej Górze, zaś kończy się w Sztynorcie. Zwroty można
robić tylko przy wyznaczonych bojami punktach. Wiadomo także, że z każdej boi można płynąć wyłącznie w
ściśle wyznaczonych kierunkach szlakami żeglownymi. Ponadto boje mają tę własność,
że z każdej z nich może prowadzić szlak tylko i wyłącznie do boi o numerach większych niż numer tej boi. W
Pięknej Górze, czyli miejscu startu stoi boja nr , zaś w Sztynorcie stoi boja nr . Wiadomo, że
każdy odcinek szlaku żeglownego łączący dwie boje ma stały podany na wejściu przechył.
Wszystkie odcinki wychodzące z Pięknej Góry, a także wchodzące do Sztynortu mają przechył 0
wobec konieczności wpływania i wypływania z portu na silniku. Zakładając, że kolejno
pokonywane odcinki mają kolejne przechyły równe , to liczba
oznacza sumaryczne wrażenia Kubusia. Twoim zadaniem jest policzyć
maksymalną wartość tej sumy.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis szlaków wędrownych
- wyliczy maksymalne wrażenia z rejsu
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu znajdują się dwie liczby całkowite oraz
oddzielone pojedynczym odstępem, przy czym , zaś .
W każdym z kolejnych wierszy znajdują się trzy liczby całkowite
, i oddzielone pojedynczymi odstępami. Liczby i oznaczają odpowiednio numery boi
połączonych tym odcinkiem. Wiadomo, że . Liczba oznacza wychylenie łódki,
przy czym . Jeśli (Piękna Góra), bądź (Sztynort), to .
Wyjście
Powinno zawierać dokładnie jedną liczbę całkowitą oznaczającą maksymalne wrażenia Kubusia z rejsu.
Przykład
Dla danych wejściowych:
6 8
1 2 0
1 3 0
2 3 10
3 4 20
4 6 0
5 6 0
4 5 10
2 5 10
poprawną odpowiedzią jest:
800
Autor zadania: Wojciech Śmietanka.