解题思路
有两段航班:
- 从城市 A 到城市 B 有 n 个航班,起飞时间为 a1,a2,…,an,飞行时间为 ta
- 从城市 B 到城市 C 有 m 个航班,起飞时间为 b1,b2,…,bm,飞行时间为 tb
小明要从 A 到 C,你可以取消总共 k 个航班。
目标是让小明最终到达 C 的时间尽量晚;如果无论如何都无法到达,则输出 −1。
P4649.第1题-取消航班
题目内容
有 A,B,C 三个城市 A 到 B 有 n 个航班,起飞时间为 ai,B 到 C 有 m 个航班,起飞时间为 bi 。每个从 A 到 B 的航班飞行时间为 ta 。每个从 B 到 C 的航班飞行时间为 tb ,如果小明乘坐起飞时间为 x 的航班,那他将在 x+ta 时间到达 B ,城市 B 同理。
小明希望从 A 飞到 C ,但你想搞一个恶作剧,你可以取消 k 个航班延迟他的到达时间。最开始,小明在城市 A 。
若可以使其无法到达请输出 −1。
输入描述
第一行五个整数 n,m,ta,tb,k。
第二行 n 个整数表示 ai。
第三行 m 个整数表示 bi。
1≤n,m≤10000,1≤ta,tb≤109,1≤a1<a2<...<an≤109,1≤b1<b2<...<bm≤109,0≤k≤n+m
输出描述
一行一个,整数表示答案,即小明最晚到达 C 的时间。
样例1
输入
3 3 1 2 2
1 5 7
2 6 8
输出
10
样例2
输入
3 3 1 2 3
1 5 7
2 6 8
输出
-1