分数: 400 点
问题陈述
高桥决定给予 一 给青木的礼物和 一 给 Snuke 的礼物。
有 N 给青木的礼物候选人,
他们的价值观是 A_1, A_2, \ldots,A_N.
有 M Snuke 礼物候选者,
他们的价值观是 B_1, B_2, \ldots,B_M.
高桥想要选择礼物,使得两份礼物的价值相差最多 D.
确定他是否可以选择这样的一对礼物。 如果可以的话,打印出所选礼物的最大价值总和。
约束
- 1\leq N,M\leq 2\times 10^5
- 1\leq A_i,B_i\leq 10^{18}
- 0\leq D \leq 10^{18}
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M D A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
输出
如果他可以选择礼物来满足条件, 打印所选礼物的最大价值总和。 如果他不能满足条件,则打印 -1.
样本输入 1
2 3 2 3 10 2 5 15
示例输出 1
8
两件礼物的价值相差最多为 2.
如果他送出有价值的礼物 3 致青木和另一个有价值的人 5 对于 Snuke,满足条件,实现最大可能的值之和。
因此, 3+5=8 。
示例输入 2
3 3 0 1 3 3 6 2 7
示例输出 2
-1
他无法选择礼物来满足条件。 请注意,一个人的礼物候选可能包含多份具有相同价值的礼物。
示例输入 3
1 1 1000000000000000000 1000000000000000000 1000000000000000000
示例输出 3
2000000000000000000
请注意,答案可能不适合 32位整数类型。
示例输入 4
8 6 1 2 5 6 5 2 1 7 9 7 2 5 5 2 4
示例输出 4
14