Kayaking

题意翻译

## 题目描述 Vadim真的很喜欢旅行。（所以）当他听说在他的小镇附近有一个皮划艇大赛的时候，是十分激动的，所以，他参加了这场皮划艇的聚会。 现在聚会已经准备好开始了他们的皮划艇之旅了，但首先，他们需要选择皮划艇。这有 $2n$ 个人（包括Vadim），并且他们有$n-1$ 个双人皮划艇（当然，每个可以坐两个人）和$2$ 个单人皮划艇。第$i$ 个人的体重是$w_i$ ，并且体重在皮划艇中是一件重要的事——如果坐在同一个双人皮划艇上的两人的体重相差太多，皮划艇就会倾覆。当然，人们想要分配他们的座位来最小化使皮划艇倾覆的可能性。 事实上，单人皮划艇的不稳定性总是$0$ ，并且双人皮划艇的不稳定性为在皮划艇上两人体重的差的绝对值。在整场旅行中的不稳定值就是所有皮划艇不稳定值的和。 帮助这个聚会找出最小的总不稳定值！ ### 输入格式： 第一行包含一个整数$n$ （$2\leq n\leq 50$ ） ，第二行包含$2n$ 个整数$w_1,w_2,\dots,w_{2n}$ ，其中$w_i$ 表示第$i$ 个的体重（$1\leq w_i\leq1000$ ） ### 输出格式： 输出一个可能的最小不稳定值 感谢@Khassar 提供的翻译

题目描述

Vadim is really keen on travelling. Recently he heard about kayaking activity near his town and became very excited about it, so he joined a party of kayakers. Now the party is ready to start its journey, but firstly they have to choose kayaks. There are $ 2·n $ people in the group (including Vadim), and they have exactly $ n-1 $ tandem kayaks (each of which, obviously, can carry two people) and $ 2 $ single kayaks. $ i $ -th person's weight is $ w_{i} $ , and weight is an important matter in kayaking — if the difference between the weights of two people that sit in the same tandem kayak is too large, then it can crash. And, of course, people want to distribute their seats in kayaks in order to minimize the chances that kayaks will crash. Formally, the instability of a single kayak is always $ 0 $ , and the instability of a tandem kayak is the absolute difference between weights of the people that are in this kayak. Instability of the whole journey is the total instability of all kayaks. Help the party to determine minimum possible total instability!

输入输出格式

输入格式

The first line contains one number $ n $ ( $ 2<=n<=50 $ ). The second line contains $ 2·n $ integer numbers $ w_{1} $ , $ w_{2} $ , ..., $ w_{2n} $ , where $ w_{i} $ is weight of person $ i $ ( $ 1<=w_{i}<=1000 $ ).

输出格式

Print minimum possible total instability.

输入输出样例

输入样例 #1

2
1 2 3 4

输出样例 #1

1

输入样例 #2

4
1 3 4 6 3 4 100 200

输出样例 #2

5