AT_joi2025_yo2_c ソフトクリーム (Softcream)

Alice と Bob はソフトクリーム屋さん JOICE に来ている．この店では，客がフレーバー・コーン・トッピングをそれぞれひとつずつ選ぶことによって，ソフトクリームを注文する． - フレーバーは $ X $ 種類あり，値段はそれぞれ $ A_1, A_2, \dots, A_X $ である． - コーンは $ Y $ 種類あり，値段はそれぞれ $ B_1, B_2, \dots, B_Y $ である． - トッピングは $ Z $ 種類あり，値段はそれぞれ $ C_1, C_2, \dots, C_Z $ である． ソフトクリームの値段は選んだフレーバー・コーン・トッピングの値段の合計となる．ここで，与えられた整数 $ P $ に対して，ソフトクリームの **スコア** をその値段と $ P $ との差の絶対値とする． Alice と Bob は $ 2 $ 人で $ 1 $ つのソフトクリームを注文しようとしているが， $ 2 $ 人がどんなソフトクリームを注文したいかは真逆である．具体的には，Alice はスコアを最大化することを，Bob はスコアを最小化することを目的としている．そこで，以下の方法で，注文するソフトクリームのフレーバー・コーン・トッピングを選ぶことにした． 1. 最初に，Alice がフレーバーを選ぶ． 2. 次に，Bob がコーンを選ぶ． 3. 最後に，Alice がトッピングを選ぶ． フレーバー，コーン，トッピングに関する情報および整数 $ P $ が与えられたとき，両者が各選択で最善を尽くした場合に最終的に注文するソフトクリームのスコアを求めるプログラムを作成せよ．

入力は以下の形式で与えられる． > $ X $ $ Y $ $ Z $ $ P $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_X $ $ B_1 $ $ B_2 $ $ \cdots $ $ B_Y $ $ C_1 $ $ C_2 $ $ \cdots $ $ C_Z $

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

### 小課題 1. ( $ 7 $ 点) $ X = 1 $ ， $ Y = 1 $ ， $ Z \leqq 100 $ ． 2. ( $ 17 $ 点) $ X = 1 $ ， $ Y \leqq 100 $ ， $ Z \leqq 100 $ ． 3. ( $ 21 $ 点) $ X \leqq 100 $ ， $ Y \leqq 100 $ ， $ Z \leqq 100 $ ． 4. ( $ 22 $ 点) $ X \leqq 4\,000 $ ， $ Y \leqq 4\,000 $ ， $ Z \leqq 4\,000 $ ． 5. ( $ 33 $ 点) 追加の制約はない． ### Sample Explanation 1 フレーバー・コーン・トッピングの選び方は以下の $ 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 $ になる． この入力例はすべての小課題の制約を満たす． ### Sample Explanation 2 フレーバー・コーン・トッピングの選び方は以下の $ 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 $ の制約を満たす． ### Sample Explanation 3 $ P=0 $ のとき，スコアは単に選んだフレーバー・コーン・トッピングの値段の合計となるので，Alice はより値段の高いフレーバー・トッピングを選び，Bob はより値段の低いコーンを選ぶのが最善である． よって，選ぶフレーバー・コーン・トッピングの値段はそれぞれ $ 23,5,45 $ であり，スコアは $ 73 $ になる． この入力例は小課題 $ 3,4,5 $ の制約を満たす． ### Sample Explanation 4 同じ値段のフレーバーやコーン，トッピングが存在する場合もある事に注意せよ． この入力例は小課題 $ 3,4,5 $ の制約を満たす． ### Constraints - $ 1 \leqq X \leqq 200\,000 $ ． - $ 1 \leqq Y \leqq 200\,000 $ ． - $ 1 \leqq Z \leqq 200\,000 $ ． - $ 0 \leqq P \leqq 3 \times 10^8 $ ． - $ 0 \leqq A_i \leqq 10^8 $ ( $ 1\leqq i \leqq X $ )． - $ 0 \leqq B_j \leqq 10^8 $ ( $ 1\leqq j \leqq Y $ )． - $ 0 \leqq C_k \leqq 10^8 $ ( $ 1\leqq k \leqq Z $ )． - 入力される値はすべて整数である．