2158 - ソフトクリーム (Softcream)

時間制限 2 秒 / メモリ制限 1024 MB / 得点 100 / Writer syoribu / x 1 / 統計 /

TLE
2sec
MLE
1024MB
得点
100

問題文

Alice と Bob はソフトクリーム屋さん JOICE に来ている．この店では，客がフレーバー・コーン・トッピングをそれぞれひとつずつ選ぶことによって，ソフトクリームを注文する．

  • フレーバーは X 種類あり，値段はそれぞれ A1, A2, …, AX である．
  • コーンは Y 種類あり，値段はそれぞれ B1, B2, …, BY である．
  • トッピングは Z 種類あり，値段はそれぞれ C1, C2, …, CZ である．

ソフトクリームの値段は選んだフレーバー・コーン・トッピングの値段の合計となる．ここで，与えられた整数 P に対して，ソフトクリームの スコア をその値段と P との差の絶対値とする．

Alice と Bob は 2 人で 1 つのソフトクリームを注文しようとしているが，2 人がどんなソフトクリームを注文したいかは真逆である．具体的には，Alice はスコアを最大化することを，Bob はスコアを最小化することを目的としている．そこで，以下の方法で，注文するソフトクリームのフレーバー・コーン・トッピングを選ぶことにした．

  1. 最初に，Alice がフレーバーを選ぶ．
  2. 次に，Bob がコーンを選ぶ．
  3. 最後に，Alice がトッピングを選ぶ．

フレーバー，コーン，トッピングに関する情報および整数 P が与えられたとき，両者が各選択で最善を尽くした場合に最終的に注文するソフトクリームのスコアを求めるプログラムを作成せよ．

制約

  • 1 ≦ X ≦ 200 000．
  • 1 ≦ Y ≦ 200 000．
  • 1 ≦ Z ≦ 200 000．
  • 0 ≦ P ≦ 3 × 108．
  • 0 ≦ Ai ≦ 108 (1≦ i ≦ X)．
  • 0 ≦ Bj ≦ 108 (1≦ j ≦ Y)．
  • 0 ≦ Ck ≦ 108 (1≦ k ≦ Z)．
  • 入力される値はすべて整数である．

小課題

  1. (7 点) X = 1， Y = 1， Z ≦ 100．
  2. (17 点) X = 1， Y ≦ 100， Z ≦ 100．
  3. (21 点) X ≦ 100， Y ≦ 100， Z ≦ 100．
  4. (22 点) X ≦ 4 000， Y ≦ 4 000， Z ≦ 4 000．
  5. (33 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
X Y Z P
A1 A2 … AX
B1 B2 … BY
C1 C2 … CZ

出力

最終的に注文するソフトクリームのスコアを 1 行で出力せよ．

入出力例

入力例 1
1 1 3 22
5
10
9 2 3

出力例 1
5

フレーバー・コーン・トッピングの選び方は以下の 3 通りある．

  • 値段がそれぞれ 5,10,9：値段は合計 24 になるので，スコアは 24 と 22 との差の絶対値である 2
  • 値段がそれぞれ 5,10,2：値段は合計 17 になるので，スコアは 17 と 22 との差の絶対値である 5
  • 値段がそれぞれ 5,10,3：値段は合計 18 になるので，スコアは 18 と 22 との差の絶対値である 4

まず Alice は値段 5 のフレーバーを選び，次に Bob は値段 10 のコーンを選ぶ．

最後に，Alice はスコアを最大化したいので，値段 2 のトッピングを選んでスコアを 5 にするのが最善である．

よって，両者が最善を尽くした場合のスコアは 5 になる．

この入力例はすべての小課題の制約を満たす．

入力例 2
1 2 2 100
11
33 44
40 60

出力例 2
15

フレーバー・コーン・トッピングの選び方は以下の 4 通りある．

  • 値段がそれぞれ 11,33,40：値段は合計 84 になるので，スコアは 84 と 100 との差の絶対値である 16
  • 値段がそれぞれ 11,33,60：値段は合計 104 になるので，スコアは 104 と 100 との差の絶対値である 4
  • 値段がそれぞれ 11,44,40：値段は合計 95 になるので，スコアは 95 と 100 との差の絶対値である 5
  • 値段がそれぞれ 11,44,60：値段は合計 115 になるので，スコアは 115 と 100 との差の絶対値である 15

まず Alice は値段 11 のフレーバーを選ぶ．

次に Bob は値段 33 のコーンと値段 44 のコーンのうちいずれかを選ぶ． ここで Bob が選んだコーンに応じて，Alice はその後スコアを最大化するために以下のような行動をとる．

  • Bob が値段 33 のコーンを選んだ場合：Alice は値段 40 のトッピングを選び，スコアを 16 にする．
  • Bob が値段 44 のコーンを選んだ場合：Alice は値段 60 のトッピングを選び，スコアを 15 にする．

Bob はスコアを最小化したいので，値段 44 のコーンを選んでスコアを 15 にするのが最善である．

よって，両者が最善を尽くした場合のスコアは 15 になる．

この入力例は小課題 2,3,4,5 の制約を満たす．

入力例 3
2 2 2 0
15 23
5 16
23 45

出力例 3
73

P=0 のとき，スコアは単に選んだフレーバー・コーン・トッピングの値段の合計となるので，Alice はより値段の高いフレーバー・トッピングを選び，Bob はより値段の低いコーンを選ぶのが最善である．

よって，選ぶフレーバー・コーン・トッピングの値段はそれぞれ 23,5,45 であり，スコアは 73 になる．

この入力例は小課題 3,4,5 の制約を満たす．

入力例 4
3 3 3 50
12 5 5
2 19 37
10 5 15

出力例 4
14

同じ値段のフレーバーやコーン，トッピングが存在する場合もある事に注意せよ．

この入力例は小課題 3,4,5 の制約を満たす．