Rozważmy graf opisujący sieć komunikacji publicznej, np. sieć autobusową, tramwajową, metra, itp. Wierzchołki grafu, o numerach 1,2,...,n, reprezentują przystanki, a krawędzie (p_i,p_j), (dla p_i <>p_j) oznaczają możliwe, bezpośrednie przejazdy od przystanku p_i do p_j (1<=p_i, p_j<=n). W sieci kursują pojazdy linii komunikacyjnych. Linie komunikacyjne oznaczone są numerami 1,2,...,k. Linia komunikacyjna l zdefiniowana jest przez ciąg przystanków p_l,1, p_l,2,...,p_l,sl, przez które przejeżdżają pojazdy linii, oraz czasy przejazdów r_l,1, r_l,2,...,r_l,sl-1 pomiędzy przystankami --- r_l,1 jest czasem przejazdu od przystanku p_l,1 do p_l,2, lub z powrotem, tj. od przystanku p_l,2 do p_l,1; r_l,2 jest czasem przejazdu od przystanku p_l,2 do p_l,3, itd. Wszystkie przystanki linii są różne, tj.\ dla i<>j zachodzi p_l,i<>p_l,j. Na danej linii l pojazdy kursują z określoną częstotliwością c_l, gdzie c_l jest liczbą ze zbioru {6, 10, 12, 15, 20, 30, 60}. Pojazdy linii wyruszają z przystanku p_l,1 o każdej okrągłej godzinie doby, g:0, (0<=g<=23), a następnie zgodnie z częstotliwością linii, a więc o godzinach g:c_l,g:2c_l,... itd. (g:c_l oznacza c_l minut po godzinie g). Ruch pojazdów linii odbywa się jednocześnie w obu kierunkach: z przystanku p_l,1 do p_l,sl, a także z przystanku p_l,sl do p_l,1. Godziny odjazdów pojazdów linii z przystanku p_l,sl są takie same, jak z przystanku p_l,1. W tak zdefiniowanej sieci komunikacji publicznej chcemy odbyć podróż z przystanku początkowego x, do przystanku końcowego y. Zakładamy, że podróż jest możliwa i nie będzie trwała dłużej niż 24 godziny. W trakcie podróży możemy się przesiadać dowolną liczbę razy z jednej linii komunikacyjnej na inną. Przyjmujemy, że czas dokonania przesiadki jest równy 0, jednakowoż, zmieniając linię musimy liczyć się z koniecznością czekania na pojazd linii, do którego chcemy się przesiąść. Naszym celem jest odbycie podróży z przystanku początkowego x, do przystanku końcowego y, w minimalnym czasie.

Przykład

Zadanie

• wczyta z pliku tekstowego POD.IN opis sieci oraz linii komunikacyjnych, numer przystanku początkowego x, numer przystanku końcowego y, godzinę początkową g_x oraz minuty początkowe m_x,
• wyznaczy minimalny czas podróży od przystanku początkowego x, do przystanku końcowego y,
• zapisze do pliku tekstowego POD.OUT najwcześniejszą możliwą godzinę z minutami dotarcia do przystanku y --- odpowiednio, g_y oraz m_y.

Wejście

• liczba przystanków n (1<=n<=1000),
• liczba linii komunikacyjnych k (1<=k<=2000),
• numer przystanku początkowego x (1<=x<=n),
• numer przystanku końcowego y (1<=y<=n),
• godzina rozpoczęcia podróży g_x (0<=g_x<=23),
• minuta rozpoczęcia podróży m_x (0<=m_x<=59).

• W pierwszym wierszu opisującym linię komunikacyjną l są zapisane dwie liczby całkowite, oddzielone pojedynczym odstępem: s_l, równa liczbie przystanków (2<=s_l<=n), oraz c_l, równa częstotliwości kursowania pojazdów (c_l należy do: {6, 10, 12, 15, 20, 30, 60}).
• W drugim wierszu opisującym linię komunikacyjną l jest zapisanych s_l różnych liczb całkowitych, pooddzielanych pojedynczymi odstępami: p_l,1,p_l,2,...,p_l,sl --- numery kolejnych przystanków na tej linii (1<=p_l,i<=n, dla 1<=i<=s_l).
• W trzecim wierszu opisującym linię komunikacyjną l jest zapisanych s_l-1 liczb całkowitych, pooddzielanych pojedynczymi odstępami: r_l,1, r_l,2,..., r_l,sl-1 --- czasy przejazdów (w minutach) pomiędzy kolejnymi przystankami na tej linii (1<=r_l,i<=240, dla 1<=i<=s_l-1).

Wyjście

Przykład

6 2 5 6 23 30
4 15
1 3 4 6
9 12 10
4 20
5 3 4 2
11 17 11

0 16