公平的礼物

题目描述

高桥决定给青木一份礼物，给斯努克一份礼物。

给青木的礼物候选有 $N$ 个，其价值分别为 $A_1, A_2, \ldots, A_N$。

给斯努克的礼物候选有 $M$ 个，其价值分别为 $B_1, B_2, \ldots, B_M$。

高桥希望选择两份礼物，使两份礼物的价值之差不超过 $D$。

判断能否选出这样的一对礼物。如果能，输出所选礼物价值之和的最大值。

输入格式

输入按以下格式从标准输入给出：

$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

数据范围

• $1 \le N,M \le 2 \times 10^5$
• $1 \le A_i,B_i \le 10^{18}$
• $0 \le D \le 10^{18}$
• 输入中的所有值均为整数。