题目描述

高橋君は青木君とすぬけ君に $1$ つずつ贈り物を送ることにしました。
青木君への贈り物の候補は $N$ 個あり、 それぞれの価値は $A_1,\ A_2,\ \ldots,A_N$ です。
すぬけ君への贈り物の候補は $M$ 個あり、 それぞれの価値は $B_1,\ B_2,\ \ldots,B_M$ です。

高橋君は $2$ 人への贈り物の価値の差が $D$ 以下になるようにしたいと考えています。

条件をみたすように贈り物を選ぶことが可能か判定し、可能な場合はそのような選び方における贈り物の価値の和の最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $D$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_M$

输出格式

高橋君が条件をみたすように贈り物を選ぶことができる場合、 条件をみたし、かつ価値の和が最大になるように贈り物を選んだ時の価値の和を出力せよ。 高橋君が条件をみたすように選ぶことができない場合、$-1$ を出力せよ。

题目大意

一个人要送礼物给另外两个人，现有 $n$ 件礼物要选一件送给第一个人，价值分别为 $a_1,a_2,\cdots,a_n$，有 $m$ 件礼物要选一件送给第二个人，价值分别为 $b_1,b_2,\cdots,b_m$。求在两件礼物之差不超过 $d$ 的情况下，价值总和的最大值。

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\ A_i,B_i\leq\ 10^{18}$
• $0\leq\ D\ \leq\ 10^{18}$
• 入力はすべて整数

Sample Explanation 1

高橋君は贈り物の価値の差を $2$ 以下にする必要があります。 青木君に価値 $3$, すぬけ君に価値 $5$ の贈り物を渡すと条件をみたし、価値の和としてはこのときが最大となります。 よって、$3+5=8$ を出力します。

Sample Explanation 2

条件をみたすように贈り物を選ぶことは不可能です。 また、同一人物に対して、同じ価値の贈り物が複数存在することもあります。

Sample Explanation 3

答えが $32$ bit整数型の範囲に収まらないことがあることに注意してください。