【题意】

有一个 $n$ 行 $n$ 列的方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。

【输入格式】

第一行是一个整数$n$ 。

第 $2$ 到第 $(n + 1)$ 行，每行 $n$ 个整数，第 $(i + 1)$ 行的第 $j$ 个整数代表方格图第 $i$ 行第 $j$ 列的的方格中的数字 $a_{i, j}$。

【输出格式】

输出一行一个整数，代表和最大是多少。

【样例输入】

3
1 2 3
3 2 3
2 3 1

【样例输出】

11

【数据规模与约定】

对于 $100\%$ 的数据，保证 $1 \leq n \leq 30$，$1 \leq a_{i, j} \leq 10^5$。