Zadanie Godzilla (god)

Godzilla

Limit pamięci: 32 MB

Godzilla znów terroryzuje Bajtoły Dolne. Każdego dnia potwór wychodzi z oceanu, powolnym ruchem kroczy przez miasto do pewnego z wieżowców i zjada go wraz z przebywającymi w nim ludźmi. Zjedzenie jednego wieżowca zajmuje jej cały dzień i o zmroku wraca ona do swej kryjówki ukrytej w głębinach. Co gorsza, idąc przez miasto, Godzilla macha ogonem i burzy wieżowce, koło których przechodzi.

Perspektywa zostania posiłkiem dla podwodnego monstrum zniechęca niektórych mieszkańców do przebywania w mieście. W ciągu nocy z każdego wieżowca wyprowadza się jeden mieszkaniec i ucieka na wieś.

W Bajtołach wieżowce zbudowane zostały jedynie przy skrzyżowaniach ulic. Przy każdym skrzyżowaniu znajduje się dokładnie jeden budynek. Skrzyżowania połączone są dwukierunkowymi ulicami. Dodatkowo jedno ze skrzyżowań jest tuż nad brzegiem oceanu, właśnie tam Godzilla rozpoczyna swą niszczycielską wędrówkę przez miasto. W jej trakcie potwór porusza się jedynie po ulicach.

Godzilla zauważyła, że musi pospieszyć się ze spożywaniem mieszkańców i uważnie dobierać wieżowce do pożarcia oraz ulice, którymi do nich dotrze. Oczywiście nigdy nie wybiera zburzonego lub wcześniej skonsumowanego wieżowca. Jaka jest maksymalna liczba osób, które może zjeść, zanim miasto kompletnie opustoszeje?

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i () oznaczające odpowiednio liczbę skrzyżowań w mieście oraz liczbę łączących je ulic. Skrzyżowania są ponumerowane liczbami od do , skrzyżowanie numer znajduje się nad brzegiem oceanu. Kolejny wiersz zawiera ciąg liczb całkowitych () opisujących liczby mieszkańców wieżowców przy poszczególnych skrzyżowaniach. W każdym z następnych wierszy są po dwie liczby całkowite i (), które oznaczają, że istnieje droga łącząca skrzyżowania i . Ze skrzyżowania numer da się dotrzeć do każdego innego skrzyżowania w mieście.