/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 を出力せよ。
入力例 1
2 3 2 3 10 2 5 15
出力例 1
8
高橋君は贈り物の価値の差を 2 以下にする必要があります。
青木君に価値 3, すぬけ君に価値 5 の贈り物を渡すと条件をみたし、価値の和としてはこのときが最大となります。
よって、3+5=8 を出力します。
入力例 2
3 3 0 1 3 3 6 2 7
出力例 2
-1
条件をみたすように贈り物を選ぶことは不可能です。 また、同一人物に対して、同じ価値の贈り物が複数存在することもあります。
入力例 3
1 1 1000000000000000000 1000000000000000000 1000000000000000000
出力例 3
2000000000000000000
答えが 32 bit整数型の範囲に収まらないことがあることに注意してください。
入力例 4
8 6 1 2 5 6 5 2 1 7 9 7 2 5 5 2 4
出力例 4
14
Score : 400 points
Problem Statement
Takahashi has decided to give one gift to Aoki and one gift to Snuke.
There are N candidates of gifts for Aoki,
and their values are A_1, A_2, \ldots,A_N.
There are M candidates of gifts for Snuke,
and their values are B_1, B_2, \ldots,B_M.
Takahashi wants to choose gifts so that the difference in values of the two gifts is at most D.
Determine if he can choose such a pair of gifts. If he can, print the maximum sum of values of the chosen gifts.
Constraints
- 1\leq N,M\leq 2\times 10^5
- 1\leq A_i,B_i\leq 10^{18}
- 0\leq D \leq 10^{18}
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M D A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
Output
If he can choose gifts to satisfy the condition, print the maximum sum of values of the chosen gifts. If he cannot satisfy the condition, print -1.
Sample Input 1
2 3 2 3 10 2 5 15
Sample Output 1
8
The difference of values of the two gifts should be at most 2.
If he gives a gift with value 3 to Aoki and another with value 5 to Snuke, the condition is satisfied, achieving the maximum possible sum of values.
Thus, 3+5=8 should be printed.
Sample Input 2
3 3 0 1 3 3 6 2 7
Sample Output 2
-1
He cannot choose gifts to satisfy the condition. Note that the candidates of gifts for a person may contain multiple gifts with the same value.
Sample Input 3
1 1 1000000000000000000 1000000000000000000 1000000000000000000
Sample Output 3
2000000000000000000
Note that the answer may not fit into a 32-bit integer type.
Sample Input 4
8 6 1 2 5 6 5 2 1 7 9 7 2 5 5 2 4
Sample Output 4
14