题目描述

在一个 $n \times n$ 的方格里，每个格子里都有一个正整数。从中取出若干数，使得任意两个取出的数所在格子没有公共边，且取出的数的总和尽量大。

输入格式

第一行一个数 $n~(n \leq 30)$ 接下来 $n$ 行每行 $n$ 个数描述一个方阵。

输出格式

仅一个数，即最大和。

2
1 2
3 5

6