[NOI2013]书法家

题目描述

小E同学非常喜欢书法,他听说NOI2013已经开始了,想题一幅“NOI”的字送给大家。 小E有一张非常神奇的纸,纸可以用一个n 行m 列的二维方格矩阵来表示,为了描述方便,我们定义矩阵左下角方格坐标为(1,1) ,右上角方格坐标为(m,n) 。矩阵的每个方格有一个整数的幸运值。在格子上面写字可以增加大家的幸运度,幸运度的大小恰好是所有被笔写到的方格的幸运值之和。现在你要在上面写上 ‘N’,‘O’,‘I’三个字母。 下面给出3个书法字的定义: 1.‘N’由若干(≥3)个边平行于坐标轴的矩形组成,设有K个矩形组成(标号1~K),第i个矩形的左下角方格坐标设为(Li ,Bi) ,右上角坐标设为(Ri ,Ti) ,要求满足: a)Li<=Ri,Bi<=Ti b)对任意1B1,T2=T1,B(K-1)=B(K),T(k-1)=3,H>=3 b)u>R(K)+1 3.‘I’为3个边平行于坐标轴的从下到上的实心矩形组成,从下到上依次标号为1,2,3,第i 个矩形的左下角格子坐标设为(Pi , Qi ),右上角格子坐标设为(Gi , Hi ),要求满足: ```cpp a)Pi<=Gi,Qi<=Hi b)P1=P3>u+W,G1=G3 c)Q1=H1=Q2-1,H2+1=Q3=H3 d)P1

输入输出格式

输入格式


输入文件penman.in的第一行包含两个正整数n和m,分别表示矩阵的行数和列数。 接下来n行,每行有m个整数,第i+1行的第j个数表示格子(j,n-i+1)的幸运值。

输出格式


输出到文件penman.out中,输出一个整数T,表示小E能够获得的最大幸运度。

输入输出样例

输入样例 #1

3 13 
1 1 -1 -1 1 -1 1 1 1 -1 1 1 1 
1 -1 1 -1 1 -1 1 -1 1 -1 -1 1 -1 
1 -1 -1 1 1 -1 1 1 1 -1 1 1 1 

输出样例 #1

24

输入样例 #2

3 13
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

输出样例 #2

-20

说明

样例1 ![](https://cdn.luogu.org/upload/pic/199.png) 样例2 ![](https://cdn.luogu.org/upload/pic/200.png) 数据范围 ![](https://cdn.luogu.org/upload/pic/201.png) 对于所有的测试数据,保证n≥3,m≥12。