AT_joi2023_yo2_b.ジョイ四人組 (JOI04)

JOI 中学有 $4N$ 名一年级学生，被分成了 4 个班。每个班级的信息如下：

• 1 年 A 班： 有 $N$ 名学生。每个学生的身高分别为 $A_1, A_2, \ldots, A_N$。
• 1 年 B 班： 有 $N$ 名学生。每个学生的身高分别为 $B_1, B_2, \ldots, B_N$。
• 1 年 C 班： 有 $N$ 名学生。每个学生的身高分别为 $C_1, C_2, \ldots, C_N$。
• 1 年 D 班： 有 $N$ 名学生。每个学生的身高分别为 $D_1, D_2, \ldots, D_N$。

下个月，JOI 中学将举办体育节。体育节包含接力赛、骑马战、推倒棒子等各种项目，而每个年级学生表演的舞蹈被称为“体育节的花”，是备受关注的项目。

在这里，一年级学生需要每个班各选出 1 人，组成 4 人小组参与舞蹈。为了让舞蹈效果尽可能协调，需要选择身高差最小的 4 人组合。

给定一年级学生的身高，请编写一个程序，求出所有可能的 4 人组合中，“4 人身高的最大值”与“4 人身高的最小值”之差的最小可能值。

输入格式如下：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_N$ $C_1$ $C_2$ $\cdots$ $C_N$ $D_1$ $D_2$ $\cdots$ $D_N$

请输出一行，表示所有可能组合中“4 人身高的最大值”与“4 人身高的最小值”之差的最小值。

子任务

1. ($7$ 分) $N = 1$。
2. ($23$ 分) $N \leq 30$。
3. ($14$ 分) $N \leq 2\,000$，且 $A_i \leq 10$、$B_j \leq 10$、$C_k \leq 10$、$D_l \leq 10$。
4. ($20$ 分) $N \leq 2\,000$，且 $A_i \leq 2\,000$、$B_j \leq 2\,000$、$C_k \leq 2\,000$、$D_l \leq 2\,000$。
5. ($13$ 分) $N \leq 2\,000$。
6. ($23$ 分) 没有额外限制。

样例解释 1

由于 $N = 1$，只能每班都选该生组成 4 人组。此时 4 人组的最大身高为 $200$，最小身高为 $152$，差值为 $200 - 152 = 48$。因此，输出 $48$。

此输入满足子任务 $1,2,4,5,6$ 的限制。

样例解释 2

此输入满足子任务 $2,3,4,5,6$ 的限制。

样例解释 3

此输入满足子任务 $2,3,4,5,6$ 的限制。

样例解释 4

此输入满足子任务 $2,4,5,6$ 的限制。

样例解释 5

此输入满足子任务 $2,5,6$ 的限制。

数据范围

• $1 \leq N \leq 75\,000$。
• $1 \leq A_i \leq 10^9$，$1 \leq i \leq N$。
• $1 \leq B_j \leq 10^9$，$1 \leq j \leq N$。
• $1 \leq C_k \leq 10^9$，$1 \leq k \leq N$。
• $1 \leq D_l \leq 10^9$，$1 \leq l \leq N$。
• 所有输入均为整数。

由 ChatGPT 5 翻译