题目描述

航拍照片被划分成 $n\times n$ 个小区域，每个区域都有一个价值评分。正数表示值得保留，负数表示会降低成片质量。

编辑需要裁出一个边与网格平行的、非空的矩形区域。请计算这个矩形能够获得的最大评分总和。

输入格式

第一行包含一个整数 $n$。

接下来 $n$ 行，每行输入 $n$ 个整数，表示评分矩阵。

输出格式

输出非空子矩形能够获得的最大评分总和。

4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

15

数据范围与提示

• $1\le n\le 120$
• 每个评分的绝对值不超过 $10^5$