103023: [Atcoder]ABC302 D - Impartial Gift

Problem Statement

Takahashi has decided to give one gift to Aoki and one gift to Snuke.
There are $N$ candidates of gifts for Aoki, and their values are $A_1, A_2, \ldots,A_N$.
There are $M$ candidates of gifts for Snuke, and their values are $B_1, B_2, \ldots,B_M$.

Takahashi wants to choose gifts so that the difference in values of the two gifts is at most $D$.

Determine if he can choose such a pair of gifts. If he can, print the maximum sum of values of the chosen gifts.

Constraints

• $1\leq N,M\leq 2\times 10^5$
• $1\leq A_i,B_i\leq 10^{18}$
• $0\leq D \leq 10^{18}$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$ $D$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_M$

Output

If he can choose gifts to satisfy the condition, print the maximum sum of values of the chosen gifts. If he cannot satisfy the condition, print $-1$.

Sample Input 1

2 3 2
3 10
2 5 15

Sample Output 1

8

The difference of values of the two gifts should be at most $2$.
If he gives a gift with value $3$ to Aoki and another with value $5$ to Snuke, the condition is satisfied, achieving the maximum possible sum of values.
Thus, $3+5=8$ should be printed.

Sample Input 2

3 3 0
1 3 3
6 2 7

Sample Output 2

-1

He cannot choose gifts to satisfy the condition. Note that the candidates of gifts for a person may contain multiple gifts with the same value.

Sample Input 3

1 1 1000000000000000000
1000000000000000000
1000000000000000000

Sample Output 3

2000000000000000000

Note that the answer may not fit into a $32$-bit integer type.

Sample Input 4

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

Sample Output 4

14

问题描述

高桥决定给青木和千石各送< strong >一份礼物< / strong >。
有$ 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。

样例输入1

2 3 2
3 10
2 5 15

样例输出1

8

两份礼物价值的差应不超过$2$。
如果他送给青木价值为$3$的礼物，送给千石价值为$5$的礼物，条件就可以满足，且可以获得最大的价值之和。
因此，应输出$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