POLSKI SPOJ

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: t₁, t₂, m, n₁, n₂ (0 ≤ t₁ ≤ t₂ ≤ 10^9; 2 ≤ m ≤ 1000; n₁, n₂ ≥ 1; m*(n₁+n₂) ≤ 10⁶), 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 n₁+n₂ liczb całkowitych x_ij (0 ≤ x_ij ≤ 10⁹), gdzie x_ij reprezentuje czas przyjazdu / odjazdu j-tego autobusu. Liczby te są pooddzielane w wierszach pojedynczymi odstępami. Dla j ≤ n₁ liczba dotyczy autobusu jadącego z zajezdni, dla j > n₁ - 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 t_A i t_B, jest możliwa, o ile t_A ≤ t_B.

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.