Score : $400$ points

问题描述

Takahashi 已决定给 Aoki 和 Snuke 各赠送 一件 礼物。
对于 Aoki，有 $N$ 件候选礼物，它们的价值分别为 $A_1, A_2, \ldots,A_N$。
对于 Snuke，有 $M$ 件候选礼物，它们的价值分别为 $B_1, B_2, \ldots,B_M$。

Takahashi 希望选择一对礼物，使得两件礼物的价值差不超过 $D$。

判断他是否可以选出满足条件的一对礼物。如果可以，则输出所选礼物价值之和的最大值。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 08:29:31