Opis

Właśnie się obudziłeś. Jest piękny poranek, słoneczko świeci wysoko, ptaszki ćwierkają. Jednak Ty masz dziwne przeświadczenie, że coś jest nie tak. Z przyzwyczajenia patrzysz na budzik... I wtedy uświadamiasz sobie, że zaspałeś. Na jednej nodze wyrywasz się z łóżka i starasz się przygotować do wyjścia. Już planujesz wychodzić kiedy uświadamiasz sobie, że jadąc na umówione spotkanie autobusem dotrzesz po zakończeniu spotkania. Dlatego też postanawiasz jechać samochodem. Tutaj jednak pojawia się problem, ile czasu będziesz musiał spędzić w samochodzie?

Zanim wyruszysz na bardzo ważne spotkanie postanawiasz odpowiedzieć sobie na to pytanie. Znając rozkład ulic i skrzyżowań w mieście masz zamiar policzyć ile co najmniej czasu zajmie Ci przejazd ze skrzyżowania, na którym zaparkowałeś samochód do skrzyżowania, przy którym masz spotkanie. Oczywiście jako uczciwy obywatel i kierowca będziesz jechał zgodnie ze wszystkimi przepisami. Tak więc jeżeli na skrzyżowaniu świeci się światło czerwone (lub zaświeciło się w momencie dojazdu do niego) to musisz poczekać aż zapali się zielone. Możesz oczywiście (ale nie musisz) skręcić w prawo korzystając z zielonej strzałki, która pali się zawsze w czasie gdy pali się światło czerwone. W momencie gdy na skrzyżowaniu pali się światło zielone, możesz przejechać przez skrzyżowanie na wprost, skręcając w lewo, prawo lub zawrócić (o ile nie obowiązuje Cię jakiś zakaz skrętu i istnieje ulica do której taki skręt miałby prowadzić). Przejazd przez skrzyżowanie (zarówno na zielonej strzałce jak i na normalnym zielonym świetle) trwa pewien określony czas, zależny od kierunku wjazdu i wyjazdu ze skrzyżowania oraz z tego, czy korzystasz z zielonej strzałki, czy z zielonego światła. W celu zwiększenia przepustowości niektórych dróg, część ulic jest jednokierunkowa (na takie ulice oczywiście nie można wjechać pod prąd). Dodatkowo czas przejazdu w jedną stronę może być różny od czasu przejazdu w drugą. W mieście jest sporo mostów i tuneli, więc nie możesz nic założyć o samych połączeniach (ulice mogą się przecinać bez konieczności istnienia skrzyżowania pomiędzy nimi). Światła na skrzyżowaniu palą się cyklicznie. Tzn. najpierw przez R sekund pali się światło czerwone, po czym następuje zmiana światła na zielone, które pali się przez kolejne G sekund. Następnie cykl się powtarza. Znasz czas, w którym rozpoczął się jeden z cykli. Sygnalizacja świetlna w tym mieście nie jest idealna. Dopuszczalna jest taka sytuacja kiedy na przykład wszystkie światła na skrzyżowaniu palą się na czerwono, lub wszystkie są zielone. Każde skrzyżowanie może mieć co najwyżej cztery ulice wlotowe i cztery ulice wylotowe - północną (N), zachodnią (W), południową (S) i wschodnią (E). Tak więc z zielonej strzałki możesz skorzystać w przypadku gdy wjeżdżasz na skrzyżowanie z północy (N) i chcesz jechać na zachód (W), lub wjeżdżasz z kierunku zachodniego (W) i jedziesz na południe (S), lub z S do E, lub z E do N. Każda droga łącząca dwa skrzyżowania ma podany pewien minimalny czas jaki potrzeba na jej przebycie.

Znając taki dokładny plan miasta ustal minimalny czas jaki będzie Ci potrzebny do przybycia na spotkanie. Zakładamy, że Twój samochód jest zaparkowany tuż przed pewnym skrzyżowaniem przez które musisz przejechać, a do którego dojazd Ci 0 sekund. Wiemy też, że na pewno istnieje możliwość dojechania z tego skrzyżowania do celu.

Specyfikacja wejścia

Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 50), oznaczającą liczbę zestawów danych. Pierwsza linia każdego zestawu danych zawiera dwie liczby całkowite N oraz M (1 ≤ N ≤ 10000, 1 ≤ M ≤ 20000) oznaczające odpowiednio liczbę skrzyżowań i liczbę dróg w mieście. Następnie znajduje się opis N skrzyżowań. Opis pojedynczego skrzyżowania znajduje się w ośmiu liniach. W pierwszej linii podane są cztery liczby Rn Rw Rs Re (1 ≤ R ≤ 200). Oznaczają one długość światła czerwonego na poszczególnych wlotach. W kolejnej linii znajdują się kolejne cztery liczby Gn Gw Gs Ge (1 ≤ G ≤ 200), oznaczające długość światła zielonego na poszczególnych wlotach. W następnej linii znajdują się cztery liczby On Ow Os Oe (0 ≤ O ≤ 200). Oznaczają one początek pewnego cyklu zmiany świateł, czyli moment, w którym zapala się światło czerwone. W kolejnej linii znajdują się cztery liczby RDn RDw RDs RDe (1 ≤ RD ≤ 200), które oznaczają czas przejazdu na zielonej strzałce z odpowiedniego wlotu. Następne cztery linie opisują czasy przejazdu przez skrzyżowanie na zielonym świetle według podanego poniżej schematu:

      Tnn Tnw Tns Tne
      Twn Tww Tws Twe
      Tsn Tsw Tss Tse
      Ten Tew Tes Tee 

Mając podany parametr Txy wiesz, że czas przejazdu z wlotu X do wylotu Y zajmie ci Txy sekund (1 ≤ Txy ≤ 100). W przypadku gdy podany czas jest ujemny musisz założyć, że niemożliwe jest przedostanie się przez skrzyżowanie danym połączeniem (może wynikać to z zakazu skrętu lub po prostu braku drogi, na którą taki skręt miałby prowadzić). W kolejnych M liniach znajduje się opis poszczególnych ulic. Każda z tych linii zawiera pięć liczb Ps Pk Ks Kk t (1 ≤ Ps,Ks ≤ N; Pk,Kk \in {N,S,W,E}; 0 ≤ t ≤ 100). Oznaczają one odpowiednio: Ps - numer skrzyżowania, z którego rozpoczyna się droga, Pk - wylot, pod który jest podczepiony początek tej drogi, Ks - numer skrzyżowania w którym kończy się dana droga, Kk - wlot, pod który podczepiony jest koniec tej drogi, oraz t - czas przejazdu tą drogą od skrzyżowania Ps do Ks. W ostatniej linii znajdują się cztery liczby A Ak B Ts, gdzie A (1 ≤ A,B ≤ N) oznacza numer skrzyżowania, przed którym zaparkowałeś samochód, zaś Ak oznacza kierunek, z którego na to skrzyżowanie wjedziesz (Ak \in {N,S,W,E}), B oznacza numer skrzyżowania na które planujesz dojechać, zaś Ts jest momentem, w którym planujesz ruszyć w drogę (0 ≤ Ts ≤ 10000). Wszystkie dane liczbowe podane w zadaniu są liczbami całkowitymi.

Specyfikacja wyjścia

Dla każdego zestawu danych na wyjściu należy wypisać w osobnej linii jedną liczbę całkowitą oznaczająca minimalny czas jaki zajmie Ci dotarcie do celu od momentu ruszenia Twojego samochodu z miejsca, na którym był on zaparkowany. Przez dotarcie do celu rozumiemy dojazd do skrzyżowania końcowego z dowolnej strony i zatrzymanie się tuż przed nim.

Przykład 1 Przykład 2