Jamboree de minijogos

É noite de festa no Reino dos Cogumelos e, como sempre, Mario e Luigi discutem quem é o melhor nos minijogos. Para resolver a questão, Mario caiu em um Espaço de Duelo e desafiou seu irmão para um minijogo especial: Blocos no canto.

O que nenhum dos dois sabia é que Bowser escondeu sob o tabuleiro o Minimizador, alimentado por um dos Cristais do Céu que roubou deles, capaz de encolher os blocos golpeados até fazê-los desaparecer.

O minijogo é jogado em um tabuleiro quadrado de $n \times n$ blocos. O bloco na linha $i$ e coluna $j$ contém $a_{i,j}$ moedas. Alguns blocos foram sabotados por Bowser: nesse caso, $a_{i,j}$ é negativo e, ao golpeá-lo, o jogador perde $|a_{i,j}|$ moedas.

Mario e Luigi jogam por turnos, começando por Mario. Em seu turno, o jogador escolhe um dos dois cantos a seguir do tabuleiro atual:

• Superior esquerdo: golpeando todos os blocos da linha superior e da coluna esquerda.

• Inferior direito: golpeando todos os blocos da linha inferior e da coluna direita.

O jogador soma as moedas de todos os blocos que golpeou (o bloco do canto é contado uma única vez). Em seguida, o Minimizador faz esses blocos desaparecerem, de modo que o tabuleiro de tamanho $k \times k$ se reduz a um de $(k - 1) \times (k - 1)$. O minijogo termina quando não restam blocos.

Ambos os irmãos jogam de forma ótima, buscando maximizar as moedas que cada um obtém.

Determine quantas moedas Mario terá ao terminar o minijogo.

Entrada

A primeira linha contém um inteiro $n$, o tamanho do tabuleiro. $(1 \leq n \leq 2000)$

As $n$ linhas seguintes contêm $n$ inteiros cada uma, separados por espaços. O $j$-ésimo inteiro da $i$-ésima linha é $a_{i,j}$, a quantidade de moedas do bloco localizado na linha $i$ e na coluna $j$. $(-10^9 \leq a_{i,j} \leq 10^9)$

Saída

Imprima um único inteiro: a quantidade de moedas que Mario terá ao terminar o minijogo, se ambos os jogadores jogarem de forma ótima.

Notas

No primeiro exemplo, o canto superior esquerdo dá mais moedas a Mario, $7 + 7 + 3 + 3 + 9 = 29$ (primeira tabela abaixo), mas Luigi responde com o mesmo canto e obtém $7 + 4 + 9 = 20$, deixando para ele um bloco com $3$. Mario terminaria com $32$.

É melhor o canto inferior direito, com $9 + 9 + 3 + 4 + 3 = 28$ moedas (segunda tabela abaixo). Luigi obtém $17$ com qualquer um dos cantos e resta a Mario um bloco com $7$, terminando com $35$.

No segundo exemplo, com o canto superior esquerdo Mario obtém $1$, Luigi fica com $9$ e resta a Mario um bloco com $-3$, terminando com $-2$. Com o inferior direito ele obtém $3$, Luigi fica com $7$ e resta a Mario $-3$, terminando com $0$.

3
7 7 3
3 7 4
9 9 3

35

3
-2 5 -1
4 -3 6
-5 1 2

0

7
-20 27 -12 27 18 7 48
-1 11 -4 -7 21 42 -7
-11 28 13 18 -5 24 40
43 -5 46 11 25 38 24
-10 -12 -9 43 19 13 8
1 21 35 44 22 21 43
31 20 2 5 39 8 24

453