问题描述

高桥君打算分别给青木君和すぬけ君各送一份礼物。

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

すぬけ君的礼物有 $M$ 个候选，每个礼物的价值分别为 $B_1, B_2, \ldots, B_M$。

高桥君希望两份礼物的价值之差不超过 $D$。请判断是否可以选择满足条件的两份礼物。如果可以，请输出在所有满足条件的选择中，礼物价值和的最大值；如果无法满足条件，则输出 $-1$。

输入格式

一行包含三个整数 $N, M, D$。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$。

第三行包含 $M$ 个整数 $B_1, B_2, \ldots, B_M$。

输出格式

如果可以选择满足条件的两份礼物，输出价值和的最大值；否则输出 $-1$。

样例输入 1

2 3 2
3 10
2 5 15

样例输出 1

8

说明：选 $A_1 = 3$ 与 $B_2 = 5$，差 $2 \le D$，和 $8$ 为最大。

样例输入 2

3 3 0
1 3 3
6 2 7

样例输出 2

-1

说明：差必须为 $0$，但没有任何一对 $A_i = B_j$。

样例输入 3

1 1 1000000000000000000
1000000000000000000
1000000000000000000

样例输出 3

2000000000000000000

说明：答案可能超出 $32$ 位整数范围，需要使用 $64$ 位整数。

样例输入 4

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

样例输出 4

14

评测数据规模

对于 $100\%$ 的数据，$1 \le N, M \le 2 \times 10^5$，$1 \le A_i, B_i \le 10^{18}$，$0 \le D \le 10^{18}$，所有输入均为整数。