1475 - 方格取数

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

输入

第一行一个数n;(n<=30)接下来n行每行n个数描述一个方阵

输出

仅一个数,即最大和

样例

输入

2
1 2
3 5

输出

6
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题