怠惰人生

題目敘述

怠惰是一件邪惡的事情，比如就像是坐在電腦螢幕前面什麼也不做的人，真是非常怠惰，因此為了讓這一些人勤勉起來，怠惰的大罪司教貝特魯吉烏斯·羅曼尼康帝決定要給這一些人一個試煉，來活動筋骨。

因為上面那個名字太長了，所以簡稱他是怠惰，真是有夠怠惰。在他的老巢裡面有一個矩形的魔法陣，由一些直線與橫線分割了這一個矩形成$N\times N$個子區域，每一個區域都有不同的魔力能量，經由怠惰的權能測定完每一個區域的魔力能量後，他希望請你在一些區域上放置魔力的結晶石來吸收魔法陣的能量，使得能量的總和最大。如果一個區域的魔力能量是$K$，那在該區域放置結晶石就能吸收$K$單位的能量，不過放置結晶石會破壞原有的魔法陣陣型，使得相鄰的八個格子(上、下、左、右、左上、右上、左下、右下)區域的魔力能量流失殆盡，直接歸零，因此慎選放置的區域十分重要，比如說下方的範例中選擇粗體紅字的區域放置會是最好的。你能完成怠惰的任務嗎？

$$ \begin{array}{|c|c|c|c|} \hline 50 & 8 & 50 & 20 \\ \hline 30 & \color{red}{\boldsymbol{90}} & 75 & \color{red}{\boldsymbol{40}} \\ \hline 13 & 15 & 30 & 80 \\ \hline \color{red}{\boldsymbol{60}} & 25 & \color{red}{\boldsymbol{65}} & 60 \\ \hline \end{array} $$

輸入說明

輸入的第一行有一個正整數$N$，代表魔法陣的大小。接下來$N$行，每行有$N$個整數，兩個整數間都以一個空格隔開，代表魔法陣中每行區域中的魔力能量。

$3\leq N \leq 22$
$0\leq 格子內的數字 \leq 1000000$。

輸出說明

請輸出該魔法陣能吸收能的魔力能量總和最大值為何。

範例輸入

4
50 8 50 20
30 90 75 40
13 15 30 80
60 25 65 60

範例輸出

配分方式:

第$i$筆測資$N=max(3,i)$，各佔5分

限制:

時限	3000ms
記憶體	128 MB

提示

Tip:DP。

Judge Setting

run-time limit: 3000 ms
memory limit: 128000000 byte
測資數量: 0