← 返回题目列表

Codeforces · 1148/B

B. 生来如此

中文机器翻译题面 查看原题

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 的最后一个航班。