← 返回题目列表

AtCoder · past19_j

J. 三人行

中文机器翻译题面 查看原题

问题陈述

有 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