Migrated from Lutece 2990 a DFS problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你知道DFS吗？

没错，就是Distributed File System。（精神错乱） 给定一个大小为 $n*n$ 的矩阵，每个位置有一个正整数，你可以从中取若干个数，满足：

记从上往下第 $x$ 行、从左往右第 $y$ 列对应的位置为 $(x,y)$，若取了 $(x,y)$处的数，则不能取 $(x+2,y),(x-2,y),(x+3,y),(x-3,y),(x,y-2),(x,y+2),(x,y-3),(x,y+3),(x+1,y+1),(x+1,y-1),(x-1,y-1),(x-1,y+1)$这 $12$ 个位置的数（如果对应位置仍然落在矩阵内）。

如上图所示，如果取出了圆圈对应位置的数，则不能取所有红叉对应位置的数。

求所有符合上述要求的取数方案中，取出来所有数之和的最大值。

Input

输入第一行包含一个整数 $n$。 接下来 $n$ 行，每行 $n$ 个数，描述了这个矩阵。

Output

输出包含一个整数，表示取出所有数之和的最大值。

Samples

7
3 2 1 2 4 5 2
1 2 3 4 2 3 2
9 6 7 4 6 9 2
1 3 4 2 3 4 5
2 3 4 5 2 1 2
9 5 8 4 2 3 1
2 3 4 5 6 3 2

57

Constraints

保证 $1\le n\le 8$，矩阵内所有数均为正整数，且大小均在区间 $[1,1000]$ 内。 保证矩阵内所有数均为随机生成。

Note

优秀的做法可以在 $50ms$ 内解决此问题，欢迎挑战。

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming