题目描述

Alice 和 Bob 来到了 JOICE 冰淇淋店。这家店的顾客可以通过选择一种口味、一种蛋筒和一种配料来订购冰淇淋。

• 口味有 $X$ 种，价格分别为 $A_1, A_2, \ldots, A_X$。
• 蛋筒有 $Y$ 种，价格分别为 $B_1, B_2, \ldots, B_Y$。
• 配料有 $Z$ 种，价格分别为 $C_1, C_2, \ldots, C_Z$。

冰淇淋的价格是所选口味、蛋筒和配料价格的总和。给定一个整数 $P$，冰淇淋的得分定义为价格与 $P$ 之差的绝对值。

Alice 和 Bob 想要一起订购一个冰淇淋，但他们对冰淇淋的选择目标完全相反。具体来说，Alice 希望最大化得分，而 Bob 希望最小化得分。因此，他们决定按照以下方式选择冰淇淋的口味、蛋筒和配料：

1. 首先，Alice 选择口味。
2. 然后，Bob 选择蛋筒。
3. 最后，Alice 选择配料。

给定口味、蛋筒、配料的信息以及整数 $P$，编写一个程序，计算当双方都采取最佳策略时，最终订购的冰淇淋的得分。

输入格式

输入按以下格式给出：

$$\begin{aligned} &X\ Y\ Z\ P\\ &A_1\ A_2\ \ldots\ A_X\\ &B_1\ B_2\ \ldots\ B_Y\\ &C_1\ C_2\ \ldots\ C_Z\\ \end{aligned} $$

输出格式

输出最终订购的冰淇淋的得分。

1 1 3 22
5
10
9 2 3

5

1 2 2 100
11
33 44
40 60

15

2 2 2 0
15 23
5 16
23 45

73

3 3 3 50
12 5 5
2 19 37
10 5 15

14

提示

样例解释

样例 1 解释

• 口味价格为 5。
• 蛋筒价格为 10。
• 配料价格分别为 9、2、3。

Alice 首先选择价格为 5 的口味，Bob 选择价格为 10 的蛋筒。最后，Alice 选择价格为 2 的配料，使得总价格为 17，得分为 $|17-22|=5$。

输入例 2 解释

• 口味价格为 11。
• 蛋筒价格分别为 33、44。
• 配料价格分别为 40、60。

Alice 选择价格为 11 的口味，Bob 选择价格为 44 的蛋筒（因为这样可以使 Alice 选择价格为 60 的配料，得分为 $|115 - 100|=15$）。

输入例 3 解释

• 口味价格分别为 15、23。
• 蛋筒价格分别为 5、16。
• 配料价格分别为 23、45。

Alice 选择价格为 23 的口味，Bob 选择价格为 5 的蛋筒，Alice 选择价格为 45 的配料，总价格为 73，得分为 $|73-0|=73$。

输入例 4 解释

• 口味价格分别为 12、5、5。
• 蛋筒价格分别为 2、19、37。
• 配料价格分别为 10、5、15。

Alice 选择价格为 12 的口味，Bob 选择价格为 2 的蛋筒，Alice 选择价格为 15 的配料，总价格为 29，得分为 $|29 - 50| = 21$。然而，Bob 会选择价格为 19 的蛋筒，使得 Alice 选择价格为 15 的配料，总价格为 46，得分为 $|46-50|=4$。但最终得分为 14，因为 Alice 会选择最优策略。

数据范围

• $1 \leq X \leq 200\,000$。
• $1 \leq Y \leq 200\,000$。
• $1 \leq Z \leq 200\,000$。
• $0 \leq P \leq 3 \times 10^8$。
• $0 \leq A_i \leq 10^8$ ($1 \leq i \leq X$)。
• $0 \leq B_j \leq 10^8$ ($1 \leq j \leq Y$)。
• $0 \leq C_k \leq 10^8$ ($1 \leq k \leq Z$)。
• 输入的所有值都是整数。

子任务

1. (7 分) $X = 1$，$Y = 1$，$Z \leq 100$。
2. (17 分) $X = 1$，$Y \leq 100$，$Z \leq 100$。
3. (21 分) $X \leq 100$，$Y \leq 100$，$Z \leq 100$。
4. (22 分) $X \leq 4\,000$，$Y \leq 4\,000$，$Z \leq 4\,000$。
5. (33 分) 无额外约束。