Arkady买了一张从A城市到C城市的机票。不幸的是,没有直飞航班,但是从A城市到B城市、从B到C城市有很多航班。
从 A 飞往 B 有 $$$n$$$ 航班,它们在 $$$a_1$$$、$$$a_2$$$、$$$a_3$$$、...、$$$a_n$$$ 时刻出发,片刻后到达 B $$$t_a$$$。
从 B 飞往 C 有 $$$m$$$ 航班,它们在 $$$b_1$$$、$$$b_2$$$、$$$b_3$$$、...、$$$b_m$$$ 时刻出发,片刻后抵达 C $$$t_b$$$。
中转时间可以忽略不计,因此可以使用从 A 到 B 的第 $$$i$$$ 航班和从 B 到 C 的第 $$$j$$$ 航班当且仅当 $$$b_j \ge a_i + t_a$$$。
您最多可以取消 $$$k$$$ 航班。如果您取消航班,阿尔卡迪将无法使用该航班。
Arkady 希望尽早进入 C,而你希望他尽可能晚进入 C。如果您最好取消 $$$k$$$ 航班,请查找 Arkady 最早可以到达 C 的时间。如果您可以取消 $$$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$$$。
否则,如果您以最大化时间的方式取消 $$$k$$$ 航班,则打印 Arkady 可以到达 C 的最早时间。
示例
输入 #1
4 5 1 1 2 1 3 5 7 1 2 3 9 10
输出 #1
11
输入 #2
2 2 4 4 2 1 10 10 20
输出 #2
-1
输入 #3
4 3 2 3 1 1 999999998 999999999 1000000000 3 4 1000000000
输出 #3
1000000003
注意
考虑第一个例子。从 A 飞往 B 的航班分别在 $$$1$$$、$$$3$$$、$$$5$$$ 和 $$$7$$$ 时刻出发,并在 $$$2$$$、$$$4$$$、$$$6$$$、$$$8$$$ 时刻到达 B。 B飞往C的航班分别在$$$1$$$、$$$2$$$、$$$3$$$、$$$9$$$、$$$10$$$时刻出发,到达C的时刻为$$$2$$$、$$$3$$$、$$$4$$$、$$$10$$$、$$$11$$$。您最多可以取消两个航班。最优方案是取消从A到B的第一个航班和从B到C的第四个航班。这样Arkady就必须乘坐从A到B的第二个航班,在$$$4$$$时刻到达B,并在$$$11$$$时刻乘坐从B到C的最后一个航班到达C。
在第二个示例中,您只需取消从 A 到 B 的所有航班即可。
在第三个示例中,您只能取消一个航班,最佳解决方案是取消从 A 到 B 的第一个航班。请注意,仍然有足够的时间赶上从 B 到 C 的最后一个航班。