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