题目描述

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

• 口味有 $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$ 之差的绝对值。

• 例如：假设选择的口味，蛋筒，配料的编号分别为 $i,j,k$。则得分为 $|a_i+b_j+c_k-p|$。

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

1. 首先，翁老师 选择口味。
2. 然后，聪聪老师 选择蛋筒。
3. 最后，翁老师 选择配料。

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

输入格式

第一行输入四个空格隔开的整数 $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$。

输出格式

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

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$。

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

样例 2 解释

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

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

注意：聪聪老师不会选择价格为 $33$ 的蛋筒，因为这样不会使得得分最小化。

样例 3 解释

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

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

样例 4 解释

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

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

数据范围

对于 $100\%$ 的数据满足：$1\leq x,y,z\leq 2\times 10^5$，$1\leq a_i,b_j,c_k\leq 10^8$，$0\leq p\leq 3\times 10^8$。

• 其中 $i\in [1,x]$，$j\in [1, y]$，$k\in [1,z]$。

本题采用捆绑测试