问题描述

高桥君想送给青木君和すぬけ君一份礼物。 他准备了两种类型的礼物：第一种有 $N$ 个，价值分别为 $A_1, A_2, \ldots, A_N$；第二种有 $M$ 个，价值分别为 $B_1, B_2, \ldots, B_M$。 高桥君打算从第一种礼物中选一个送给青木君，从第二种礼物中选一个送给すぬけ君。 为了让两个人都高兴，他希望两份礼物的价值差不超过 $D$。 即，需要满足 $|A_i - B_j| \leq D$。

请判断能否选出满足条件的两份礼物。如果可以，请输出在这种情况下两份礼物的价值总和的最大值；如果无法选出，则输出 -1。

输入格式

第一行输入三个数$N$ $M$ $D$ 第二行输入n个数$A_1$ $A_2$ $\ldots$ $A_N$ 第三行输入m个数$B_1$ $B_2$ $\ldots$ $B_M$

输出格式

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

2 3 2
3 10
2 5 15

8

3 3 0
1 3 3
6 2 7

-1

1 1 1000000000000000000
1000000000000000000
1000000000000000000

2000000000000000000

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 D \leq 10^{18}$
• $1 \leq A_i, B_j \leq 10^{18}$
• 输入中的所有值均为整数。