레이팅 미적용Alice と Bob はソフトクリーム屋さん JOICE に来ている.この店では,客がフレーバー・コーン・トッピングをそれぞれひとつずつ選ぶことによって,ソフトクリームを注文する.
フレーバーは X 種類あり,値段はそれぞれ A 1 , A 2 , ..., A X である.
コーンは Y 種類あり,値段はそれぞれ B 1 , B 2 , ..., B Y である.
トッピングは Z 種類あり,値段はそれぞれ C 1 , C 2 , ..., C Z である.
ソフトクリームの値段は選んだフレーバー・コーン・トッピングの値段の合計となる.ここで,与えられた整数 P に対して,ソフトクリームの スコア をその値段と P との差の絶対値とする.
Alice と Bob は 2 人で 1 つのソフトクリームを注文しようとしているが, 2 人がどんなソフトクリームを注文したいかは真逆である.具体的には,Alice はスコアを最大化することを,Bob はスコアを最小化することを目的としている.そこで,以下の方法で,注文するソフトクリームのフレーバー・コーン・トッピングを選ぶことにした.
最初に,Alice がフレーバーを選ぶ.
次に,Bob がコーンを選ぶ.
最後に,Alice がトッピングを選ぶ.
フレーバー,コーン,トッピングに関する情報および整数 P が与えられたとき,両者が各選択で最善を尽くした場合に最終的に注文するソフトクリームのスコアを求めるプログラムを作成せよ.
1 ≦ X ≦ 200 000 .
1 ≦ Y ≦ 200 000 .
1 ≦ Z ≦ 200 000 .
0 ≦ P ≦ 3 × 10 8 .
0 ≦ A i ≦ 10 8 ( \(1 \le i \le X\) ).
0 ≦ B j ≦ 10 8 ( \(1 \le j \le Y\) ).
0 ≦ C k ≦ 10 8 ( \(1 \le k \le Z\) ).
入力される値はすべて整数である.
( 7 点) X = 1 , Y = 1 , \(Z \le 100\) .
( 17 点) X = 1 , \(Y \le 100\) , \(Z \le 100\) .
( 21 点) \(X \le 100\) , \(Y \le 100\) , \(Z \le 100\) .
( 22 点) X ≦ 4 000 , Y ≦ 4 000 , Z ≦ 4 000 .
( 33 点) 追加の制約はない.
入力は以下の形式で与えられる.
X Y Z P
A 1 A 2 ... A X
B 1 B 2 ... B Y
C 1 C 2 ... C Z
最終的に注文するソフトクリームのスコアを 1 行で出力せよ.
1 1 3 22
5
10
9 2 3
5
1 2 2 100
11
33 44
40 60
15
2 2 2 0
15 23
5 16
23 45
73
3 3 3 50
12 5 5
2 19 37
10 5 15
14