소프트크림

문제

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은 두 사람이 함께 $1$ 개의 소프트크림을 주문하려고 하는데, 두 사람이 원하는 소프트크림은 정반대이다. 구체적으로, Alice는 점수를 최대화하는 것을, Bob은 점수를 최소화하는 것을 목적으로 한다. 그래서 다음과 같은 방법으로 주문할 소프트크림의 맛·콘·토핑을 고르기로 하였다.

1. 처음에 Alice가 맛을 고른다.
2. 다음으로 Bob이 콘을 고른다.
3. 마지막으로 Alice가 토핑을 고른다.

맛, 콘, 토핑에 관한 정보 및 정수 $P$ 가 주어졌을 때, 두 사람이 각 선택에서 최선을 다했을 경우 최종적으로 주문하게 되는 소프트크림의 점수를 구하는 프로그램을 작성하시오.

제한

• $1 \le X \le 200\,000$.
• $1 \le Y \le 200\,000$.
• $1 \le Z \le 200\,000$.
• $0 \le P \le 3 \times 10^{8}$.
• $0 \le A_{i} \le 10^{8}$ ($1 \le i \le X$).
• $0 \le B_{j} \le 10^{8}$ ($1 \le j \le Y$).
• $0 \le C_{k} \le 10^{8}$ ($1 \le k \le Z$).
• 입력되는 값은 모두 정수이다.

서브태스크

1. ($7$ 점) $X = 1$, $Y = 1$, $Z \le 100$.
2. ($17$ 점) $X = 1$, $Y \le 100$, $Z \le 100$.
3. ($21$ 점) $X \le 100$, $Y \le 100$, $Z \le 100$.
4. ($22$ 점) $X \le 4\,000$, $Y \le 4\,000$, $Z \le 4\,000$.
5. ($33$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 주어진다.
$X$ $Y$ $Z$ $P$
$A_{1}$ $A_{2}$ $\dots$ $A_{X}$
$B_{1}$ $B_{2}$ $\dots$ $B_{Y}$
$C_{1}$ $C_{2}$ $\dots$ $C_{Z}$

출력

최종적으로 주문하게 되는 소프트크림의 점수를 $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$ 의 제약을 만족한다.