# Appreciation

/*
 * Problem :: 17779 / 게리맨더링 2
 *
 * Kind :: Brute Force + Simulation
 *
 * Insight
 * - 선거구를 나누는 방법이 1번부터 4번까지 주어지는데
 *   4번에서 "5번 선거구에 포함되지 않은 구역 (r,c)의 선거구 번호는 다음 기준을 따른다"
 *   며 각 선거구에 포함되는 구역들을 친절히 알려주길래
 *   그럼 그냥 5번 선거구는 저 선거구들에 포함되지 않는 구역아닌가? 싶어
 *   if (1번 선거구 조건)
 *   else if (2번 선거구 조건)
 *   else if (3번 선거구 조건)
 *   else if (4번 선거구 조건)
 *   else -> 5번 선거구
 *   겠거니 했지만...
 *   + x=2, y=4, d1=2, d2=2 에서
 *     위처럼 로직을 짜게되면
 *     (2,4) 가 1번 선거구에 들어가게 돼버린다
 *     역시나 이런 꼼수는 통하지 않았다
 *
 * - 일단 선거구를 나누는 방법에서
 *   2번까지는 해당칸에 체크하면 되므로 쉽다
 *   근데 3번이 문제다
 *   경계선과 경계선 안에 포함되어있는 곳은 어떻게 체크해야하나...
 *   + 처음엔 BFS 로 해결했다
 *     일단 모든 칸을 5번 선거구에 해당하는 것으로 생각하고
 *     (1,1), (N,1), (1,N), (N,N) 는 5번 선거구가 될 수 없는 칸들이니
 *     이 칸들을 시작으로 BFS 를 돌아 실제 5번 선구구에 해당하는 칸들을 구별했다
 *     근데 시간이 너무 많이 걸리더라
 *   + 더 효율적이고 간단한 방법이 없나 생각하다가
 *     2번에서 경계선 그을 때
 *     맨 윗칸과 맨 아랫칸 제외 2-1 과 2-2 에 해당하는 칸들의 바로 오른쪽칸들은
 *     무조건 5번 선거구에 포함되며
 *     그 칸으로부터 오른쪽으로 한칸씩 이동하며
 *     2-3 과 2-4 에 해당하는 칸들에 만나기 전까지의 칸들이 모두
 *     5번 선거구안의 칸들이라는 사실을 알아냈다!
 *     # BFS 는 모든 칸을 확인해야하지만
 *       위의 방법은 이중 for 문만 돌며 5번 선거구 내의 칸들만 확인하므로
 *       훨씬 빠르고 효율적인 방법이었다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int N;
int A[20+1][20+1];
int B[20+1][20+1];

// Set up : Functions Declaration
int diff(int d1, int d2, int x, int y);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> N;
    for (int i=1; i<=N; i++)
        for (int j=1; j<=N; j++)
            cin >> A[i][j];

    // Process
    int ans = -1;
    for (int d1=1; d1<N; d1++) {
        for (int d2=1; d2<N; d2++) {
            for (int x=1; x+d1+d2<=N; x++) {
                for (int y=1+d1; y+d2<=N; y++) {
                    int tmp = diff(d1, d2, x, y);
                    if (ans == -1 || ans > tmp) {
                        ans = tmp;
                    }
                }
            }
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
int diff(int d1, int d2, int x, int y)
/* 기준점 (x,y) 와 경계의 길이 d1, d2 을 바탕으로 나뉘어진 5개 선거구에서
 * 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이 계산 */
{
    /* B[i][j] = 해당 구역의 선거구 번호 */
    memset(B, 0, sizeof(B));
    /* 경계선 그리기 */
    for (int i=0; i<=d1; i++)
        B[x+i][y-i] = 5; /* 2-1 */
    for (int i=0; i<=d2; i++)
        B[x+i][y+i] = 5; /* 2-2 */
    for (int i=0; i<=d2; i++)
        B[x+d1+i][y-d1+i] = 5; /* 2-3 */
    for (int i=0; i<=d1; i++)
        B[x+d2+i][y+d2-i] = 5; /* 2-4 */

    /* 경계선 안 구역들을 5번 선거구로 체크 */
    for (int i=0; i<d1; i++) {
        for (int j=1; B[x+i+j][y-i] != 5; j++) {
            B[x+i+j][y-i] = 5; /* 맨 윗칸 제외 2-1 경계선 칸들의 바로 오른쪽 칸들에서
                                * 오른쪽으로 한칸씩 이동하여
                                * 2-3 경계선 칸들을 만날때까지의 칸들이
                                * 경계선 안 구역들로 5번 선거구에 해당 */
        }
    }
    for (int i=1; i<d2; i++) {
        for (int j=1; B[x+i+j][y+i] != 5; j++) {
            B[x+i+j][y+i] = 5; /* 맨 아랫칸 제외 2-2 경계선 칸들의 바로 오른쪽 칸들에서
                                * 오른쪽으로 한칸씩 이동하여
                                * 2-4 경계선 칸들을 만날때까지의 칸들이
                                * 경계선 안 구역들로 5번 선거구에 해당 */
        }
    }

    int s1, s2, s3, s4, s5; /* 각 선거구의 인구수 */
    s1 = s2 = s3 = s4 = s5 = 0;
    for (int r=1; r<=N; r++) {
        for (int c=1; c<=N; c++) {
            if (B[r][c] == 5)
                s5 += A[r][c];
            else if (1 <= r && r < x+d1 && 1 <= c && c <= y)
                s1 += A[r][c];
            else if (1 <= r && r <= x+d2 && y < c && c <= N)
                s2 += A[r][c];
            else if (x+d1 <= r && r <= N && 1 <= c && c < y-d1+d2)
                s3 += A[r][c];
            else if (x+d2 < r && r <= N && y-d1+d2 <= c && c <= N)
                s4 += A[r][c];
        }
    }

    auto S = {s1, s2, s3, s4, s5};
    return max(S) - min(S);
}