Online Judge
6114 - 202602 SACCC:六级第三题 繁花（flower）
苏智来到了一片灿烂的花海,这片花海由原神打理,修理成了一个 n × m 的矩形每朵花都有一个好看值,苏智喜欢好看的花。 苏智和原神达成了一笔交易,原神给了苏智一张神奇的网,这张网只能网住一个”口“形区域,并且苏智只能带走”口型“区域边缘的花。换言之,苏智需要选出一个区域 (i 1 , j 1 ), (i 2 , j 2 ) (分别表示左上角和右下角),然后获得 (i 1 , j 1 ), (i 1+ 1, j 1 ), ...(i 2 , j 1 ), (i 1 , j 2 ), (i 1 +1, j 2 ), ...(i 2 , j 2 )(i 1 , j 1 + 1), (i 1 , j 1 + 2), ..., (i 1 , j 2 − 1), (i 2 , j 1 + 1), (i 2 , j 1 +2), ..., (i 1 , j 2 − 1) 上的花, 1 ≤ i 1 < i 2 ≤ n, 1 ≤ j 1 < j 2 ≤ m 。 苏智希望最后获得的花的好看值之和最大。请你用C++写一个AI程序每次替苏智自动计算出这个结果!
Input
第一行两个整数 n, m 接下来 n 行,每行 m 个数,表示花的美丽值 a i,j
Output
一个整数,表示获得的花的好看值之和的最大值
Examples
Input
5 4 3 -2 -2 -4 0 4 2 1 5 -1 0 -2 -6 -1 1 -1 1 3 -1 0
Output
10
Hint
样例解释:选择子矩阵 0 4 2 5 -1 0 此时和最大为10
对于 30% 的数据, 2 ≤ n, m ≤ 10 对于 50% 的数据, 2 ≤ n, m ≤ 100 。 对于 100% 的数据, 2≤ n, m ≤ 10^5 , n × m ≤ 2 × 10^5 , ∣a i,j ∣ ≤ 100。