J - Balanced Team Division Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

問題文

1 から 3N までの番号がついた 3N 人の人がいます。人 i は A_i 円持っています。
3N 人を N 組の 3 人組に分けます。i 番目の組に含まれる人の所持金の金額の総和を S_i 円とします。
3N 人をうまく N 組に分けたとき、\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 組目に人 1, 人 2, 人 6 を、2 組目に人 3, 人 4, 人 5 を割り当てると、

  • 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

Problem Statement

There are 3N people numbered from 1 to 3N. Person i has A_i yen (currency in Japan).
You are going to group the 3N people into N groups of three people each. Let S_i be the total amount of yen in the i-th group.
Find the minimum possible \displaystyle \max_{1 \leq k \leq N} S_k - \min_{1 \leq k \leq N}S_k.

Constraints

  • 2 \leq N \leq 5
  • 0 \leq A_i \leq 10^8
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_{3N}

Output

Print the minimum possible \displaystyle \max_{1 \leq k \leq N} S_k - \min_{1 \leq k \leq N}S_k.

Sample Input 1

2
1 3 4 6 2 9

Sample Output 1

1

If you group person 1, person 2, and person 6 into group 1, and person 3, person 4, and person 5 into group 2, then

  • 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.

No grouping makes \displaystyle \max_{1 \leq k \leq N} S_k - \min_{1 \leq k \leq N}S_k less than 1, so the answer is 1.

Sample Input 2

2
0 0 0 0 0 100000000

Sample Output 2

100000000

Sample Input 3

5
614 490 420 945 613 585 760 38 926 725 667 685 449 455 873

Sample Output 3

35