当前没有测试数据。

D - 公平的礼物

得分：400分

问题描述

高桥决定给青木一个礼物，并给春私一个礼物。
青木有$N$个礼物候选人， 其价值从$A_1, A_2,\ldots,A_N$。 春私有$M$个礼物候选人， 其价值从$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$。

2 3 2
3 10
2 5 15

8

两个礼物的价值之差至多应为2。
如果他给青木一个3的价值的礼物，并给春私一个5的价值的礼物，条件满足，达到最大可能的总价值。
因此，应该输出3 + 5 = 8。

3 3 0
1 3 3
6 2 7

-1

他无法选择满足条件的礼物。 注意，一个人的礼物候选人可能包含多个相同价值的礼物。

1 1 1000000000000000000
1000000000000000000
1000000000000000000

2000000000000000000

请注意，答案可能不适合32位整数类型。

8 6 1
2 5 6 5 2 1 7 9
7 2 5 5 2 4

14