题目描述

高桥君打算分别给青木君和すぬけ君各送一份礼物。
青木君的礼物有 $N$ 个候选，每个礼物的价值分别为 $A_1, A_2, \ldots, A_N$。
すぬけ君的礼物有 $M$ 个候选，每个礼物的价值分别为 $B_1, B_2, \ldots, B_M$。

高桥君希望两份礼物的价值之差不超过 $D$。

请判断是否可以选择满足条件的两份礼物。如果可以，请输出在所有满足条件的选择中，礼物价值和的最大值；如果无法满足条件，则输出 $-1$。

输入格式

输入以如下格式从标准输入读入。

$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

输出

8

样例 2

输入

3 3 0
1 3 3
6 2 7

输出

-1

样例 3

输入

1 1 1000000000000000000
1000000000000000000
1000000000000000000

输出

2000000000000000000

样例 4

输入

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

输出

14

说明/提示

限制条件

• $1 \leq N, M \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq 10^{18}$
• $0 \leq D \leq 10^{18}$
• 输入均为整数

样例解释 1

高桥君需要让两份礼物的价值之差不超过 $2$。如果给青木君价值为 $3$ 的礼物，给すぬけ君价值为 $5$ 的礼物，则满足条件，并且此时价值和最大。因此输出 $3+5=8$。

样例解释 2

无法选择满足条件的礼物。另外，同一个人可能有多个价值相同的礼物。

样例解释 3

请注意，答案可能超出 $32$ 位整数型的范围。

由 ChatGPT 4.1 翻译