配点 : $400$ 点

問題文

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

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

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

制約

• $1\leq N,M\leq 2\times 10^5$
• $1\leq A_i,B_i\leq 10^{18}$
• $0\leq D \leq 10^{18}$
• 入力はすべて整数

入力

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

$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$ bit整数型の範囲に収まらないことがあることに注意してください。

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

14