Baekjoon-17149-게리맨더링 2

N = int(input())
A = [[0]*(N+1)] + [[0] + list(map(int,input().split())) for _ in range(N)]

def get_min(x,y,d1,d2):
    result = [0,0,0,0,0]
    border = [[0]*(N+1) for _ in range(N+1)]
    for i in range(d1+1):
        border[x+i][y-i] = 1
        border[x+d2+i][y+d2-i] = 1
    for i in range(d2+1):
        border[x+i][y+i] = 1
        border[x+d1+i][y-d1+i] = 1
    for i in range(x+1,x+d1+d2):
        res_1 = 0
        for j in range(1,N+1):
            res_1 += border[i][j]
            if res_1 % 2 == 1:
                border[i][j] = 1

    for r in range(1,N+1):
        res_1 = 0
        for c in range(1,N+1):
            if border[r][c] == 1:
                result[4] += A[r][c]
            else:
                if 1<=r <x+d1 and 1<=c<=y:
                    result[0] += A[r][c]
                elif 1<=r<=x+d2 and y<c<=N:
                    result[1] += A[r][c]
                elif x+d1<=r<=N and 1<=c<y-d1+d2:
                    result[2] += A[r][c]
                elif x+d2<r<=N and y-d1+d2<=c<=N:
                    result[3] += A[r][c]
    
    # print('---',x,y,d1,d2,'---')
    # print(result)
    # print(*border,sep='\n')

    return max(result)-min(result)        

answer = int(1e5)
# answer_detail = []
for d1 in range(1,N+1):
    for d2 in range(1,N-d1):
        for x in range(1,N-d1-d2+1):
            for y in range(d1+1,N-d2+1):
                min_ = get_min(x,y,d1,d2)
                if min_ < answer:
                    answer = min_
                    # answer_detail = [x,y,d1,d2]

print(answer)