/ WHOJ / 题库 /

欢乐

欢乐

题目描述

小镇中有很多道路,四通八达。它有 n+1n+1 条的小路为南北方向,有 m+1m+1 条的小路为东西方向,这些道路将 Q 镇划分成了 m×nm×n 个区域,而这些区域,从北到南、从西到东的坐标标识为从坐标 (1,1)(1,1) 到坐标 (m,n)(m,n)

现在给出对这 m×nm×n 个区域的打分 V(i,j)V(i,j)(分数可正可负)。为了方便编程,我们选定一个连续的区域集合。我们游玩的欢乐值则为这些范围的区域评分总和。

请自己选定一个范围,在这个区域里欢乐值的最大。

格式

输入格式

输入第一行为整数 mnm,n,用空格隔开
接下来有 mm 行,每行有 nn 列整数,其中第 ii 行第 jj 列的整数,代表 V(i,j)V(i,j),一个整数之间用空格隔开。输入数据保证这些整数中,至少存在一个正整数。

输出格式

输出只有一行,为最高的欢乐值。

样例1

输入样例1

4 5
1 -2 3 -4 5
6 7 8 9 10
-11 12 13 14 -15
16 17 18 19 20

输出样例1

146

限制

对于 100%100\% 的数据,1N,M2001 ≤ N, M ≤ 200 ,且 V(i,j)[200000,200000]V(i,j)∈[-200000,200000]