问题陈述
有 3N 人数来自 1 to 3N.人 i 有 A_i 日元(日本货币)。
您要将 3N 人成 N 每组三人。 S_i 是日元的总金额 i第组。
找到可能的最小值 \displaystyle \max_{1 \leq k \leq N} S_k - \min_{1 \leq k \leq N}S_k.
约束
- 2 \leq N \leq 5
- 0 \leq A_i \leq 10^8
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 \dots A_{3N}
输出
打印尽可能少的内容 \displaystyle \max_{1 \leq k \leq N} S_k - \min_{1 \leq k \leq N}S_k.
示例输入 1
2 1 3 4 6 2 9
示例输出 1
1
如果您将人分组 1, 人 2和人 6 进组 1和人 3, 人 4和人 5 进组 2,然后
- S_1 = 1 + 3 + 9 = 13,
- S_2 = 4 + 6 + 2 = 12,
- \displaystyle \max_{1 \leq k \leq N} S_k - \min_{1 \leq k \leq N}S_k = 13 - 12 = 1.
没有分组使得 \displaystyle \max_{1 \leq k \leq N} S_k - \min_{1 \leq k \leq N}S_k 小于 1,所以答案是 1.
示例输入 2
2 0 0 0 0 0 100000000
示例输出 2
100000000
示例输入 3
5 614 490 420 945 613 585 760 38 926 725 667 685 449 455 873
示例输出 3
35