Fox Ciel has a board with n rows and n columns, there is one integer in each cell.

It's known that n is an odd number, so let's introduce <image>. Fox Ciel can do the following operation many times: she choose a sub-board with size x rows and x columns, then all numbers in it will be multiplied by -1.

Return the maximal sum of numbers in the board that she can get by these operations.

Input

The first line contains an integer n, (1 ≤ n ≤ 33, and n is an odd integer) — the size of the board.

Each of the next n lines contains n integers — the numbers in the board. Each number doesn't exceed 1000 by its absolute value.

Output

Output a single integer: the maximal sum of numbers in the board that can be accomplished.

Examples

Input

3
-1 -1 1
-1 1 -1
1 -1 -1


Output

9


Input

5
-2 0 0 0 -2
0 -2 0 -2 0
0 0 -2 0 0
0 -2 0 -2 0
-2 0 0 0 -2


Output

18

Note

In the first test, we can apply this operation twice: first on the top left 2 × 2 sub-board, then on the bottom right 2 × 2 sub-board. Then all numbers will become positive.

<image>
import java.util.Scanner;
import java.io.OutputStream;
import java.io.IOException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.io.FileInputStream;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Mike Lee
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		/*try {
			inputStream = new FileInputStream("boardgame.in");
		} catch (IOException e) {
			throw new RuntimeException(e);
		} */
		OutputStream outputStream = System.out;
		/*try {
			outputStream = new FileOutputStream("boardgame.out");
		} catch (IOException e) {
			throw new RuntimeException(e);
		} */
		Scanner in = new Scanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		BoardGame solver = new BoardGame();
		solver.solve(1, in, out);
		out.close();
	}
}

class BoardGame {
    final int kInf = Integer.MIN_VALUE;

    public void solve(int testNumber, Scanner in, PrintWriter out) {
        int n = in.nextInt(), x = n / 2;
        int[][] board = new int[n][n];
        int[] a = new int[n];
        int[][] f = new int[n / 2][2];

        int ans = -kInf;

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                board[i][j] = in.nextInt();
        for (int s = 0; s < (1 << (x + 1)); s++) {
            for (int i = 0; i <= x; i++)
                a[i] = (s & (1 << i)) > 0 ? 1 : -1;
            for (int i = x + 1; i < n; i++)
                a[i] = a[x] * a[i - x - 1];

            for (int i = 0; i < n / 2; i++)
                f[i][0] = f[i][1] = 0;

            for (int i = 0; i < x; i++)
                for (int j = 0; j < x; j++) {
                    int val1 = board[i][j] + board[i][j + x + 1] * a[i] + board[i + x + 1][j] + board[i + x + 1][j + x + 1] * a[i] * a[x];
                    int val2 = board[i][j] + board[i][j + x + 1] * a[i] + board[i + x + 1][j] * -1 + board[i + x + 1][j + x + 1] * a[i] * a[x] * -1;

                    val1 = Math.max(val1, -val1);
                    val2 = Math.max(val2, -val2);

                    f[j][0] += val1;
                    f[j][1] += val2;
                }
            for (int i = 0; i < n / 2; i++) {
                f[i][0] += board[x][i] + board[x][i + x + 1] * a[x];
                f[i][1] += -board[x][i] - board[x][i + x + 1] * a[x];
            }

            int tmp = 0;
            for (int i = 0; i < n; i++)
                tmp += a[i] * board[i][x];
            for (int i = 0; i < x; i++)
                tmp += Math.max(f[i][0], f[i][1]);

            ans = Math.max(ans, tmp);
        }
        out.print(ans);
    }
}
