ソフトクリーム (Softcream)

시간 제한2초메모리 제한2048 MB

요약

앨리스가 프레이버를, 밥이 콘을, 다시 앨리스가 토핑을 고를 때 양쪽이 최선을 다한 최종 점수를 구한다.

난이도: 보통10점 중 6점
유형: 수학, 그리디, 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

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

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

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

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

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

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

입력

入力は以下の形式で与えられる．

X Y Z P
A1 A2 … AX
B1 B2 … BY
C1 C2 … CZ

출력

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

제한

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)．
入力される値はすべて整数である．

예제4

예제 1
입력
```
1 1 3 22
5
10
9 2 3
```
예상 출력
```
5
```
예제 2
입력
```
1 2 2 100
11
33 44
40 60
```
예상 출력
```
15
```
예제 3
입력
```
2 2 2 0
15 23
5 16
23 45
```
예상 출력
```
73
```
예제 4
입력
```
3 3 3 50
12 5 5
2 19 37
10 5 15
```
예상 출력
```
14
```