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