#11060. 你还会想起这道题吗(another version)

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

众所周知,原神是由米哈游自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「提瓦特」的幻想世界,在这里,被神选中的人将被授予「神之眼」,导引元素之力。你将扮演一位名为「旅行者」的神秘角色,在自由的旅行中邂逅性格各异、能力独特的同伴们,和他们一起击败强敌,找回失散的亲人——同时,逐步发掘「原神」的真相。

之前,你作为异世界的旅行者,发现了一个富含元素能量的神秘正方形矩阵,并邂逅了一位性格迥异、能力独特的同伴——lwy。

你费尽千辛帮助他集齐了能量,然而——

”准备受死吧!异乡人!!!“只见lwy法杖一挥,天空剧变,乌云密布,万物俱灭。矩阵外围的一层墙壁开始迅速向里收缩,你即将被碾死!

”为什么……为什么要这么对我!“

随着lwy法杖的挥舞,法杖内的能量被彻底释放,神秘正方形矩阵又重新蕴含能量焕发活力。可,墙壁还在快速的逼近!!!你突然意识到,当墙壁所占之处有足够多的能量上时,你可以积聚这些能量,将墙壁彻底粉碎!

那么——聪明的旅行者,请快速的找到墙壁最多处在多少能量上,并在此处积聚能量将墙壁彻底击碎。

“可是……你为什么要这么对我……“

输入格式

第一行输入一个正整数n,表示一个n × n的矩阵大小

接下来输入一个n × n的矩阵,表示矩阵各个位置所具有的能量值

输出格式

输出一个整数,表示墙壁最多能处在多少能量上,并在此处积聚能量将墙壁彻底击碎

样例

输入样例 1

5
1 1 1 1 1
1 8 9 8 1 
1 8 3 8 1
1 8 8 8 1
1 1 1 1 1

输出样例 1

65

说明:

最外层:1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=16

中间层:8+8+8+8+8+8+8+9=65

最里层:3

所以当墙壁收缩到中间层时,能量最多,为65。

数据范围与提示

1 ≤ n ≤ 500

保证矩阵的各个位置的元素均为正整数,且不超过1000