In [1]:

    

from itertools import permutations, combinations
def cal(li):
    value = 0
    for first,second in list(permutations(li,2)):
        value = value + ability[first][second]
    return value
def start_link(n,ability):
    num_list = [i for i in range(n)]
    one = list(set(combinations(num_list,n//2)))
    two = list(permutations(one,2))
    double = two[:]
    for tdx in range(len(two)):
        for num in two[tdx][0]:
            if num in two[tdx][1]:
                idx = double.index(two[tdx])
                del double[idx]
                break
    final=[]
    for teams in double:
        result=[]
        for team in teams:
            result.append(cal(team))
        final.append(abs(result[0]-result[1]))
    return min(final)

n = int(input())
ability = []
for i in range(n):
    ab = list(map(int,input().split()))
    ability.append(ab)
start_link(n,ability)


    

    




6
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0






    
Out[1]:





2

In [2]:

    

n = int(input())
ability = []
for i in range(n):
    ab = list(map(int,input().split()))
    ability.append(ab)
start_link(n,ability)


    

    




4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0






    
Out[2]:





0

In [3]:

    

n = int(input())
ability = []
for i in range(n):
    ab = list(map(int,input().split()))
    ability.append(ab)
start_link(n,ability)


    

    




8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0






    
Out[3]:





1