B. Born This Way
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аркадий купил авиабилет из города A в город C. К сожалению, прямых рейсов нет, но есть много рейсов из A в город B, а также из B в C.

Всего есть $$$n$$$ рейсов из A в B, они вылетают в моменты времени $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, ..., $$$a_n$$$ и прилетают в B $$$t_a$$$ моментов времени спустя.

Всего есть $$$m$$$ рейсов из B в C, они вылетают в моменты времени $$$b_1$$$, $$$b_2$$$, $$$b_3$$$, ..., $$$b_m$$$ и прилетают в C $$$t_b$$$ моментов времени спустя.

Временем пересадки можно пренебречь, поэтому можно использовать $$$i$$$-й рейс из A в B и $$$j$$$-й рейс из B в C, если и только если $$$b_j \ge a_i + t_a$$$.

Вы можете отменить не более $$$k$$$ рейсов. Если вы отменяете рейс, Аркадий не сможет его использовать.

Аркадий хочет попасть в C как можно раньше, а вы хотите, чтобы Аркадий оказался в C как можно позже. Найдите самый ранний момент времени, когда Аркадий сможет попасть в C, если вы оптимально отмените $$$k$$$ рейсов. Если можно отменить $$$k$$$ или меньше рейсов так, что попасть в C станет невозможно, выведите $$$-1$$$.

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

Первая строка содержит пять целых чисел $$$n$$$, $$$m$$$, $$$t_a$$$, $$$t_b$$$ и $$$k$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$1 \le k \le n + m$$$, $$$1 \le t_a, t_b \le 10^9$$$) — количество рейсов из A и B, количество рейсов из B в C, время полета из A в B, время полета из B в C и максимальное число рейсов, которое вы можете отменить, соответственно.

Вторая строка содержит $$$n$$$ различных целых чисел в возрастающем порядке: $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, ..., $$$a_n$$$ ($$$1 \le a_1 < a_2 < \ldots < a_n \le 10^9$$$) — времена, в которые рейсы вылетают из A в B.

Третья строка содержит $$$m$$$ различных целых чисел в возрастающем порядке: $$$b_1$$$, $$$b_2$$$, $$$b_3$$$, ..., $$$b_m$$$ ($$$1 \le b_1 < b_2 < \ldots < b_m \le 10^9$$$) — времена, в которые рейсы вылетают из B в C.

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

Если можно отменить $$$k$$$ или меньше рейсов так, что попасть в C невозможно, выведите $$$-1$$$.

Иначе выведите минимальное время, в которое Аркадий сможет оказаться в C, если вы оптимальным образом отмените $$$k$$$ рейсов так, чтобы максимизировать это время.

Примеры
Входные данные
4 5 1 1 2
1 3 5 7
1 2 3 9 10
Выходные данные
11
Входные данные
2 2 4 4 2
1 10
10 20
Выходные данные
-1
Входные данные
4 3 2 3 1
1 999999998 999999999 1000000000
3 4 1000000000
Выходные данные
1000000003
Примечание

Рассмотрим первый пример. Рейсы из A в B отправляются в моменты времени $$$1$$$, $$$3$$$, $$$5$$$ и $$$7$$$ и прибывают в B в моменты времени $$$2$$$, $$$4$$$, $$$6$$$, $$$8$$$, соответственно. Рейсы из B в C вылетают в моменты времени $$$1$$$, $$$2$$$, $$$3$$$, $$$9$$$ и $$$10$$$ и прилетают в C в моменты времени $$$2$$$, $$$3$$$, $$$4$$$, $$$10$$$, $$$11$$$, соответственно. Вы можете отменить не более двух рейсов. Оптимальный выбор — отменить первый рейс из A в B и четвертый рейс из B в C. Тогда Аркадий сможет использовать первый рейс из A в B, прибыть в B в момент времени $$$4$$$, затем использовать последний рейс из B в C и прибыть в C в момент времени $$$11$$$.

Во втором примере можно просто отменить все рейсы из A в B.

В третьем примере можно отменить лишь один рейс, и оптимально отменить первый рейс из A в B. Обратите внимание, что времени как раз достаточно, чтобы успеть на последний рейс из B в C.