Аркадий купил авиабилет из города 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\).
Выходные данные
Если можно отменить \(k\) или меньше рейсов так, что попасть в C невозможно, выведите \(-1\).
Иначе выведите минимальное время, в которое Аркадий сможет оказаться в C, если вы оптимальным образом отмените \(k\) рейсов так, чтобы максимизировать это время.
Примечание
Рассмотрим первый пример. Рейсы из 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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5 1 1 2
1 3 5 7
1 2 3 9 10
|
11
|
|
2
|
2 2 4 4 2
1 10
10 20
|
-1
|
|
3
|
4 3 2 3 1
1 999999998 999999999 1000000000
3 4 1000000000
|
1000000003
|