方格取数

题目描述

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

---

输入格式

第一行一个数n；（n<=30） 接下来n行每行n个数描述一个方阵

---

输出格式

仅一个数，即最大和

---

样例输入

2
1 2
3 5

---

样例输出

6

---

提示

没有写明提示

---

题目来源

没有写明来源