第 2 题 冰淇淋 (softcream)

时间限制 1.0 s · 空间限制 256 MB · 139 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 softcream.in，输出文件 softcream.out。

题目描述

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$，编写一个程序，计算当双方都采取最佳策略时，最终订购的冰淇淋的得分。

输入格式

输入按以下格式给出：

输出格式

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

样例

样例 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

提示

样例解释

样例 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 \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 4000$，$Y \le 4000$，$Z \le 4000$。
5. (33 分) 无额外约束。