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! 


-----Input-----

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


-----Output-----

Print minimum possible total instability.


-----Examples-----
Input
2
1 2 3 4

Output
1

Input
4
1 3 4 6 3 4 100 200

Output
5

Difficulty: interview

Starter code:

Solutions:
n = int(input())
#n = 2*n
x = list(map(int, input().split()))

x.sort()

mn = 10**10
for a in range(2*n):
	for b in range(a+1, 2*n):
		# exclude a, b
		p = x[:a] + x[a+1:b] + x[b+1:]
		#print(a, b, p)
		sm = 0
		for i in range(n-1):
			sm += p[2*i+1] - p[2*i]
		mn = min(mn, sm)

print(mn)



N = 2*int(input())
W = list(map(int,input().split()))
W.sort()

from itertools import combinations

def it():

  for i,j in combinations(list(range(N)),r=2):
    k = 0
    cnt = 0
    w = None
    for k in range(N):
      if not (k == i or k == j):
        if w is None:
          w = W[k]
        else:
          cnt += abs(w-W[k])
          w = None

    yield cnt

print(min(it()))


def solve():

    n = int(input())
    w = [int(st) for st in input().split(" ")]
    w.sort()

    ans = 2**31
    ansi, ansj = None, None
    for i in range(0, 2*n-1, 2):
        for j in range(i+1, 2*n, 2):
            # pick i and j
            #print("Looking", i, j)
            s = 0
            for k in range(0, i-1, 2):
                #print(k, k+1)
                s += w[k+1] - w[k]
            for k in range(i+1, j-1, 2):
                #print(k, k+1)
                s += w[k+1] - w[k]
            for k in range(j+1, 2*n-1, 2):
                #print(k, k+1)
                s += w[k+1] - w[k]

            if s < ans:
                ans = s
                ansi = i
                ansj = j
                
    #print(ansi, ansj)

    return ans

print(solve())


n = int(input())
w = list(map(int, input().split()))
w.sort()
ans = 50000
for i in range(2 * n - 1):
    for j in range(i + 1, 2 * n):
        tmp = 0
        for k in range(2 * n):
            if k < i or j < k:
                if k % 2 == 0:
                    tmp -= w[k]
                else:
                    tmp += w[k]
            elif i < k < j:
                if k % 2 == 1:
                    tmp -= w[k]
                else:
                    tmp += w[k]
        ans = min(ans, tmp)
print(ans)


n = int(input())
a = list(map(int, input().split()))

a.sort()
cap = []
res = []
for i in range(0, 2*n - 1, 2):
    for j in range(i+1, 2*n, 2):
        f = 0
        first = 1
        cap = []
        for k in range(2*n):
            if k == i or k == j:
                continue
            if first:
                f = a[k]
                first = 0
            else:
                first = 1
                cap.append(abs(a[k] - f))
        result = sum(cap)
        res.append(result)

print(min(res))




n = int(input())
n *= 2
a = [int(i) for i in input().split()]
a.sort()
ans = 100000000
for i in range(n):
    for j in range(i + 1, n):
        b = a[:i] + a[i+1:j] + a[j + 1:]
        cr = 0
        for k in range(1, len(b), 2):
            cr += b[k] - b[k - 1]
        ans = min(ans, cr)
print(ans)


n=int(input())
w=list(map(int,input().split()))
w.sort()
stab1=0
stab2=0
stab3=0
stabmin=99999999999999999

for i in range(2*n):
    for j in range(i+1,2*n):
        temp=w.copy()
        del temp[i]
        del temp[j-1]
        stab1=0
        
        for k in range(n-1):
            stab1+=temp[2*k+1]-temp[2*k]
        stabmin=min(stab1,stabmin)
print(stabmin)


n = int(input())
a = list(map(int, input().split()))
a.sort()
an = 10 ** 9

for i in range(2 * n):
    for j in range(i + 1, 2 * n):
        if i == j:
            continue
        b = a[:]
        del b[j], b[i]
        c = 0
        for k in range(0, 2 * n - 2, 2):
            c += abs(b[k] - b[k + 1])
        an = min(an, c)
        #print(an, b)
print(an)


n = int(input())
s = list(map(int, input().split()))
s = list(sorted(s))
ansm = 100000000
for i in range(len(s)):
    s1 = s[:i] + s[i+1:]
    for j in range(len(s1)):
        s2 = s1[:j]+s1[j+1:]
        ans = 0
        for i in range(1, 2*n - 2, 2):
            ans += s2[i] - s2[i-1]
        if ans < ansm:
            ansm = ans
print(ansm)

#!/usr/bin/env python3
# encoding: utf-8



#----------
# Constants
#----------



#----------
# Functions
#----------

# Reads a string from stdin, splits it by space chars, converts each
# substring to int, adds it to a list and returns the list as a result.
def get_ints():
    return [ int(n) for n in input().split() ]


# Reads a string from stdin, splits it by space chars, converts each substring
# to floating point numbber, adds it to a list and returns the list as a result.
def get_floats():
    return [ float(n) for n in input().split() ]


def calc(w, rid):
    plus = True
    val = 0
    for i, t in enumerate(w):
        if i not in rid:
            if plus:
                val += t
            else:
                val -= t
            plus = not plus
    return val


#----------
# Execution start point
#----------

def __starting_point():
    a = get_ints()
    assert len(a) == 1
    n = a[0]
    count = 2 * n

    w = get_ints()
    assert len(w) == count
    w.sort(reverse=True)

    best = list()
    for i in range(count):
        for j in range(i+1, count):
            best.append(calc(w, [i, j]))

    print(min(best))

__starting_point()

n = int(input())
v = [int(i) for i in input().split()]
v = sorted(v)

def dp(i, chosen):
    if chosen == 0:
        d = 0
        while i < len(v):
            d += v[i+1] - v[i]
            i += 2
        return d
    if i >= len(v) - 1:
        return 0
    return min(v[i+1] - v[i] + dp(i+2, chosen), dp(i+1, chosen-1))

print(dp(0, 2))


import itertools
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=10000000
for i in range(2*n):
    for j in range(i+1,2*n):
        x=0
        b=a+[]
        del b[i],b[j-1]
        for k in range(0,2*(n-1),2):
            x+=abs(b[k]-b[k+1])
        if x<ans:
            ans=x
print(ans)
            


n = int(input())
w = list(map(int,input().split()))
w.sort()
instability = list()
for i in range(2*n):
    for j in range(i+1, 2*n):
        cnt = 0
        for k in range(2*n):
            if k < i or k > j:
                if k % 2 == 0:
                    cnt -= w[k]
                else:
                    cnt += w[k]
            if k > i and k < j:
                if k % 2 == 0:
                    cnt += w[k]
                else:
                    cnt -= w[k]
        instability.append(cnt)
print(min(instability))
                
                
        


n = int(input())

w = sorted(map(int, input().split()))
ans = 1e100
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		prev = -1
		s = 0
		for k in range(2 * n):
			if k == i or k == j:
				continue
			if prev == -1:
				prev = w[k]
			else:
				s += w[k] - prev
				prev = -1
		ans = min(ans, s)
print(ans)

n = int(input())

w = sorted(map(int, input().split()))
ans = 1e100
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		prev = -1
		s = 0
		for k in range(2 * n):
			if k == i or k == j:
				continue
			if prev == -1:
				prev = w[k]
			else:
				s += w[k] - prev
				prev = -1
		ans = min(ans, s)
print(ans)

from itertools import combinations, chain
from math import inf

def take(s):
    return sum([abs(s[i] - s[i+1]) for i in range(0, 2*n-2, 2)])

n = int(input())
wi = sorted(map(int, input().split()))
minimum = inf
for lonely_couple in combinations(list(range(2*n)), 2):
    sample = list(chain(wi[:lonely_couple[0]], wi[lonely_couple[0]+1:lonely_couple[1]], wi[lonely_couple[1]+1:]))
    minimum = min(minimum, take(sample))
print(minimum)



"""
4
1 3 4 6 3 4 1000 200
"""


from sys import stdin, stdout

n = int(stdin.readline())
values = sorted(list(map(int, stdin.readline().split())))
ans = float('inf')

for i in range(2 * n):
    for j in range(i + 1, 2 * n):     
        res = []
        
        for z in range(2 * n):
            if z == i or z == j:
                continue
            
            res.append(values[z])
        
        cnt = 0
        for q in range(0, len(res), 2):
            cnt += res[q + 1] - res[q]
        
        ans = min(ans, cnt)

stdout.write(str(ans))

n = int(input())
arr = [int(el) for el in input().split()]
arr.sort()
d_rez = []
m = 99999999
l = len(arr)
for i in range(0, l - 1):
    for j in range(i + 1, l):
        a = arr.pop(i)
        b = arr.pop(j - 1)
        size = l - 2
        diff = []
        s = 0

        for h in range(0,size,2):
            s = s + arr[h+1]-arr[h]

        if s < m:
            m = s
            d_rez = arr
        arr.append(a)
        arr.append(b)
        arr.sort()
print(m)

def readln(): return list(map(int, input().rstrip().split()))


def cal(dt):
    rs = 0
    for i in range(len(dt) // 2):
        rs += abs(dt[2 * i] - dt[2 * i + 1])
    return rs


n = int(input())
data = list(readln())
data.sort()

minw = 500000

for i in range(0, 2 * n - 1):
    for j in range(i + 1, 2 * n):
        dt = list(data)
        dt.pop(max(i, j))
        dt.pop(min(i, j))
        rs = cal(dt)
        if rs < minw:
            minw = rs

print(minw)


n=2*int(input())
w=sorted(map(int,input().split()))
r=10000
for i in range(n):
    wi=w.pop(i)
    for j in range(i):
        wj=w.pop(j)
        d=[w[i+1]-w[i] for i in range(0,n-3,2)]
        r=min(r,sum(d))
        w.insert(j,wj)
    w.insert(i,wi)
print(r)


n=2*int(input())
w=sorted(map(int,input().split()))
r=10000
for i in range(n):
    wi=w.pop(i)
    for j in range(i):
        wj=w.pop(j)
        r=min(r,sum(w[i+1]-w[i] for i in range(0,n-3,2)))
        w.insert(j,wj)
    w.insert(i,wi)
print(r)


n = int(input())
val = list(map(int, input().split()))
val.sort()
b_a = 10 ** 9
for i in range(len(val) - 1):
    for j in range(i + 1, len(val)):
        if i == j:
            continue
        ans = 0
        a, b = val[i], val[j]
        val.pop(j)
        val.pop(i)
        ans = 0
        for k in range(len(val)):
            if k % 2 == 0:
                ans += abs(val[k + 1] - val[k])
        b_a = min(b_a, ans)
        val.insert(i, a)
        val.insert(j, b)
print(b_a)

n = int(input())
w = list(map(int, input().split()))

w.sort()

d = []

# Решаем перебором, выбрасываем из списка 2 каякеров и
# находим сумму разностей весов у оставшихся, отсортированных по возрастанию
for i in range(0, 2 * n):
    for j in range(i + 1, 2 * n):
        if i == j:
            continue

        tw = list(w)
        tw.pop(i)
        tw.pop(j - 1)

        td = 0  
        for k in range(0, len(tw), 2):
            td += tw[k + 1] - tw[k]

        d.append(td)

print(min(d))


n=2*int(input())
w=sorted(map(int,input().split()))
r=10000
for i in range(n):
    for j in range(i):
        u=[w[k] for k in range(n) if i!=k!=j]
        r=min(r,sum(u[i+1]-u[i] for i in range(0,n-3,2)))
print(r)


n=2*int(input())
w=sorted(map(int,input().split()))
r=10000
for i in range(n):
    for j in range(i):
        u=w[:j]+w[j+1:i]+w[i+1:]
        r=min(r,sum(u[i+1]-u[i] for i in range(0,n-3,2)))
print(r)