Дощ#4307
В Батумі не завжди буває сонячно: море є море, і іноді на місто несподівано може налетіти справжній шторм. Резо, один з організаторів Кубка Векуа, чекав на автостанції прибуття гостей на міжміському автобусі, коли почалась сильна злива. На вулиці стояти не можна, а у приміщенні автостанції затіяли ремонт. І тут Резо звернув увагу на повний розклад міського автобуса по усім зупинкам, який висів на стіні автостанції: якщо сісти на станції у автобус цього маршруту, проїхати на ньому декілька зупинок, потім вийти і сісти на зустрічний автобус того ж маршруту так, щоб встигнути на автостанцію до прибуття гостей. При цьому Резо хоче провести під дощем якомога менше часу.
Ваша задача — порахувати цей час.
У першому рядку вхідного файлу задано чисел t_1, t_2, , n_1, n_2 (0 \leq t_1 \leq t_2 \leq 10^9, 2 \leq m \leq 1000, n_1 \geq 1, n_2 \geq 1, m\cdot(n_1+n_2) \leq 10^6). t_1 — час початку зливи, t_2 — час прибуття гостей на автостанцію, — кількість зупинок на маршруті міського автобуса (включаючи автостанцію), n_1 та n_2 — кількість рейсів міського автобуса, які йдуть від автостанції і до автостанції відповідно. Кінцевими пунктами маршруту є автостанція і зупинка з номером , залишатись в автобусі у кінцевому пункті не можна. Далі в рядках записано розклад автобусів по кожній із зупинок, перерахованих послідовно у напрямку від автостанції до кінцевої зупинки — n_1+n_2 невід’ємних цілих чисел, які не перевищують 10^9. Перші n_1 чисел позначають час відправлення автобусів, які йдуть від автостанції: -те число позначає час прибуття та відправлення -го "прямого рейсу" з даної зупинки, наступні n_2 — час прибуття та відправлення автобусів, які йдуть до автостанції: (n_1+i)-те число позначає час відправлення -го "зворотного" рейсу з даної зупинки. Вважається, що автобус прибуває і відправляється з зупинки у ту ж одиницю часу, зокрема. Резо може пересісти з автобуса на автобус, лише якщо час прибуття першого автобуса на зупинку не перевищує час прибуття другого автобуса.
Виведіть ціле число — мінімальний час, який Резо буде змушений провести під дощем до прибуття команди.
Приклад 1