eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Дождь

Дождь

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

В Батуми не всегда бывает солнечно: море есть море, и иногда на город неожиданно может налететь настоящий шторм. Резо, один из организаторов Кубка Векуа, ждал на автостанции прибытия гостей на междугороднем автобусе, когда пошёл сильный ливень. На улице стоять нельзя, а в здании автостанции затеяли ремонт. И тут Резо обратил внимание на полное расписание городского автобуса по всем остановкам, висевшее на стене автостанции: если сесть на станции в автобус этого маршрута, проехать на нём несколько остановок, потом выйти и сесть на встречный автобус того же маршрута так, чтобы успеть на автостанцию к прибытию гостей. При этом Резо хочет провести под дождём как можно меньше времени.

Ваша задача - посчитать это время.

Входные данные

В первой строке входного файла заданы 5 чисел t_1, t_2, m, n_1, n_2 (0t_1t_210^9, 2m1000, n_1, n_21,m·(n_1+n_2)10^6). t_1 - время начала ливня, t_2 - время прибытия гостей на автостанцию, m - количество остановок на маршруте внутригородского автобуса (включающее автостанцию), n_1 и n_2 - количество рейсов внутригородского автобуса, идущих с автостанции и до автостанции соответственно. Конечными пунктами маршрута являются автостанция и остановка с номером m, оставаться в автобусе на конечном пункте нельзя. Далее в m строках записаны расписания автобусов по каждой из остановок, перечисленных последовательно в направлении от автостанции к конечной остановке - n_1+n_2 неотрицательных целых чисел, не превосходящих 10^9. Первые n_1 чисел обозначают время отправления автобусов, идущих от автостанции: i-е число обозначает время прибытия и отправления i-го "прямого рейса" с данной остановки, следующие n_2 - время прибытия и отправления автобусов, идущих к автостанции: (n_1+i)-е число обозначает время отправления i-го "обратного" рейса с данной остановки. Считается, что автобус прибывает и отправляется с остановки в ту же единицу времени, в частности. Резо может пересесть с автобуса на автобус, только если время прибытия первого автобуса на остановку не превосходит времени прибытия второго автобуса.

Выходные данные

Выведите целое число - минимальное время, которое Резо вынужден будет провести под дождём до прибытия команды

Пример

Входные данные #1
0 10 3 1 2
0 9 10
3 4 8
4 3 7
Выходные данные #1
2
Источник III MSU-CBOSS Open Cup in programming. Grand Prix of South Caucasus, April 29, 2007