Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PA07_AUT - Autobusy

Mały Jaś wybiera się ze swoim kolegą do muzeum. Umówili się na spotkanie przy zajezdni autobusowej. Jaś jest osobą bardzo punktualną, w związku z czym na miejsce spotkania dotarł za wcześnie. Na dworze jest zimno, dlatego Jaś postanowił czekać na swojego znajomego w autobusie. Niestety wszystkie autobusy zatrzymują się w zajezdni tylko na chwilę, zatem Jaś postanowił wsiąść do jednego z autobusów, przejechać nim pewną liczbę przystanków, a następnie przesiąść się do autobusu jadącego z powrotem do zajezdni. Ze względu na niską temperaturę, Jaś chciałby spędzić na dworze tak mało czasu, jak to tylko możliwe. W tym celu planuje zminimalizować sumaryczny czas czekania na autobus w zajezdni, czas potrzebny na przesiadkę oraz czas oczekiwania na swojego przyjaciela po powrocie do zajezdni (ze względu na swą wrodzoną punktualność, Jaś nie mógłby spóźnić się na spotkanie z kolegą). Jaś znalazł szczegółowy rozkład jazdy autobusów, który pozwoli mu zaplanować przejażdżkę. Ponieważ jednak nie jest on dobrym matematykiem, więc poprosił Ciebie o rozwiązanie swojego problemu.

Napisz program, który wyznaczy najkrótszy czas, jaki Jaś musi spędzić na dworze czekając na kolegę.

Wejście

W pierwszym wierszu wejścia znajduje się pięć liczb całkowitych: t1, t2, m, n1, n2 (0 ≤ t1 ≤ t2 ≤ 109; 2 ≤ m ≤ 1000; n1, n2 ≥ 1; m*(n1+n2) ≤ 106), pooddzielanych pojedynczymi odstępami. Liczby te reprezentują odpowiednio: chwilę przybycia Jasia na miejsce spotkania, chwilę przybycia kolegi Jasia na miejsce spotkania, liczbę przystanków autobusowych na trasie (wliczając w to zajezdnię), liczbę autobusów jadących z zajezdni oraz liczbę autobusów jadących do zajezdni. Kolejnych m wierszy zawiera rozkłady jazdy autobusów dla kolejnych przystanków na trasie. Pierwszym przystankiem jest zajezdnia. Autobusy jadące z zajezdni zatrzymują się kolejno na przystankach 1, 2, ..., m, natomiast autobusy wracające do zajezdni - na tych samych przystankach, ale w odwrotnej kolejności. Każdy autobus po dojeździe do stacji pierwszej albo m-tej kończy kursowanie w rozważanym dniu. Rozkład jazdy na i-tym przystanku składa się z n1+n2 liczb całkowitych xij (0 ≤ xij ≤ 109), gdzie xij reprezentuje czas przyjazdu / odjazdu j-tego autobusu. Liczby te są pooddzielane w wierszach pojedynczymi odstępami. Dla jn1 liczba dotyczy autobusu jadącego z zajezdni, dla j > n1 - do zajezdni. Przybycie i odjazd każdego autobusu na każdym przystanku odbywają się w tej samej jednostce czasu. Każdy autobus potrzebuje co najmniej jednej jednostki czasu na przejechanie pomiędzy kolejnymi przystankami na swojej trasie. Jaś może wsiąść do autobusu, o ile znajduje się na przystanku w momencie odjazdu tego autobusu. W szczególności, przesiadka z autobusu A do B, jeżeli chwile ich przyjazdu na przystanek to odpowiednio tA i tB, jest możliwa, o ile tAtB.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać dokładnie jedną liczbę całkowitą - najkrótszy czas, jaki Jaś musi spędzić na dworze, czekając na swojego kolegę. Jeżeli nie istnieje para autobusów, z użyciem których można wykonać opisany manewr, to należy przyjąć, że Jaś będzie cały czas oczekiwał na kolegę przy zajezdni.

Przykład

Wejście:

0 10 3 1 2
0 9 10
3 4 8
4 3 7

Wyjście:

2

Wyjaśnienie przykładu:

W rozwiązaniu o minimalnym czasie oczekiwania Jaś wsiada na zajezdni w zerowej jednostce czasu do pierwszego autobusu, przejeżdża nim do drugiego przystanku, w czwartej jednostce czasu, wsiada w autobus powrotny o numerze dwa i dociera z powrotem do zajezdni w dziewiątej jednostce czasu.


Dodane przez:Rafal Nowak
Data dodania:2007-04-20
Limit czasu wykonania programu:1s-3s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:Potyczki Algorytmiczne 2007 (kwiecień)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.