← 返回题目列表

Codeforces · 863/B

B. 皮划艇

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

Vadim 非常热衷于旅行。最近,他听说家乡附近有皮划艇活动,对此感到非常兴奋,因此他加入了一个皮划艇爱好者的聚会。

现在队伍已经准备好开始旅程,但首先他们必须选择皮划艇。团体中有 2·n 个人(包括 Vadim),他们正好有 n - 1 艘双人皮划艇(显然,每艘皮划艇可载两人)和 2 艘单人皮划艇。第 i 个人的体重为 wi,而重量是皮划艇运动中的一个重要问题——如果坐在同一艘双人皮划艇上的两个人的体重相差太大,那么它可能会崩溃。当然,人们希望在皮划艇上分配座位,以尽量减少皮划艇发生事故的可能性。

形式上,单个皮划艇的不稳定性始终为 0,而串联皮划艇的不稳定性是皮划艇中人员体重之间的绝对差。整个旅程的不稳定是所有皮划艇的总不稳定。

帮助当事人确定最小可能的总体不稳定!

输入

第一行包含一个数字 n (2 ≤ n ≤ 50)。

第二行包含 2·n 个整数 w1, w2, ..., w2n,其中 wi 是人 i 的体重 (1 ≤ wi ≤ 1000)。

输出

打印最小可能的总体不稳定性。

示例

输入 #1

2
1 2 3 4

输出 #1

1

输入 #2

4
1 3 4 6 3 4 100 200

输出 #2

5