아이스크림 가게 JOICE timer 2초 memory 1024MB

입력은 다음과 같은 형식으로 주어진다.

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 ≦ X ≦ 200, 000

• 1 ≦ Y ≦ 200, 000

• 1 ≦ Z ≦ 200, 000

• 0 ≦ P ≦ 3 × 10^8

• 0 ≦ A_i ≦ 10^8 (1≦ i ≦ X)

• 0 ≦ B_j ≦ 10^8 (1≦ j ≦ Y)

• 0 ≦ C_k ≦ 10^8 (1≦ k ≦ Z)

첫 줄에 최종적으로 주문하는 소프트 아이스크림의 점수를 출력하시오.

맛, 콘, 토핑을 선택하는 방법은 다음과 같은 3가지가 있습니다:

1. 가격이 각각 5, 10, 9일 경우: 가격 합계는 24로, 점수는 24와 22의 차이의 절대값인 2입니다.

2. 가격이 각각 5, 10, 2일 경우: 가격 합계는 17로, 점수는 17과 22의 차이의 절대값인 5입니다.

3. 가격이 각각 5, 10, 3일 경우: 가격 합계는 18로, 점수는 18과 22의 차이의 절대값인 4입니다.

우선 앨리스는 가격 5의 맛을 선택하고, 그 다음 밥은 가격 10의 콘을 선택합니다.

마지막으로 앨리스는 점수를 최대화하려고 하므로, 가격 2의 토핑을 선택하여 점수를 5로 만드는 것이 최선입니다.

따라서 두 사람이 최선의 선택을 했을 경우의 점수는 5입니다.

이 입력 예시는 모든 소과제의 제약을 만족합니다.

맛, 콘, 토핑을 선택하는 방법은 다음과 같은 4가지가 있습니다:

1. 가격이 각각 11, 33, 40일 경우: 가격 합계는 84로, 점수는 84와 100의 차이의 절대값인 16입니다.

2. 가격이 각각 11, 33, 60일 경우: 가격 합계는 104로, 점수는 104와 100의 차이의 절대값인 4입니다.

3. 가격이 각각 11, 44, 40일 경우: 가격 합계는 95로, 점수는 95와 100의 차이의 절대값인 5입니다.

4. 가격이 각각 11, 44, 60일 경우: 가격 합계는 115로, 점수는 115와 100의 차이의 절대값인 15입니다.

먼저 앨리스는 가격 11의 맛을 선택합니다.

그 다음, 밥은 가격 33의 콘과 가격 44의 콘 중에서 하나를 선택합니다. 여기서 밥이 선택한 콘에 따라 앨리스는 그 후 점수를 최대화하기 위해 아래와 같이 행동합니다.

• 밥이 가격 33의 콘을 선택한 경우: 앨리스는 가격 40의 토핑을 선택하여 점수를 16으로 만듭니다.

• 밥이 가격 44의 콘을 선택한 경우: 앨리스는 가격 60의 토핑을 선택하여 점수를 15로 만듭니다.

밥은 점수를 최소화하고 싶기 때문에 가격 44의 콘을 선택하여 점수를 15로 만드는 것이 최선입니다.

따라서 두 사람이 최선의 선택을 했을 경우의 점수는 15입니다.

이 입력 예시는 서브테스크 2, 3, 4, 5의 제약을 만족합니다.

P=0일 경우, 점수는 단순히 선택한 맛, 콘, 토핑의 가격 합계가 됩니다. 따라서 앨리스는 더 높은 가격의 맛과 토핑을 선택하고, 밥은 더 낮은 가격의 콘을 선택하는 것이 최선입니다.

따라서 선택한 맛, 콘, 토핑의 가격은 각각 23, 5, 45이며, 점수는 73이 됩니다.