【题意】

给出一个 $N \times N$ 矩阵 $a_{ij}$。

选若干个数，使得最后所选的数和最大。

限制条件：选了某个数，那么该数 八个方向 上 相邻 的数都不能选。

【输入格式】

第一行一个整数 $N \ (3 \le N \le 15)$

下来矩阵 $a_{i,j} \ (10 \le a_{ij} \le 99)$ 。

【输出格式】

输出一个整数，表示选出的数的和的最大值。

5
71 24 95 56 54
85 50 74 94 28
92 96 23 71 10
23 61 31 30 46
64 33 32 95 89

572