#P1398. [NOI2013] 书法家

[NOI2013] 书法家

题目描述

小 E 同学非常喜欢书法,他听说 NOI2013 已经开始了,想题一幅 “NOI” 的字送给大家。

小 E 有一张非常神奇的纸,纸可以用一个 nnmm 列的二维方格矩阵来表示,为了描述方便,我们定义矩阵左下角方格坐标为 (1,1)(1,1),右上角方格坐标为 (m,n)(m, n)

矩阵的每个方格有一个整数的幸运值。在格子上面写字可以增加大家的幸运度,幸运度的大小恰好是所有被笔写到的方格的幸运值之和。现在你要在上面写 上 NOI 三个字母。

下面给出 33 个书法字的定义:

  • N 由若干(3\ge 3)个边平行于坐标轴的矩形组成,设由 KK 个矩形组成(标号 1K1 \ldots K),第 ii 个矩形的左下角方格坐标设为 (Li,Bi)(L_i, B_i),右上角坐标设为 (Ri,Ti)(R_i, T_i ),要求满足:
    1. LiRi,BiTiL_i \le R_i, B_i \le T_i
    2. 对任意 1<iK1 < i \le K,有 Li=Ri1+1L_i = R_{i-1} + 1
    3. 对任意 3i<K3 \le i < K,有 Bi11TiTi1B_{i−1} − 1 \le T_i \le T_{i-1}BiBi1B_i \le B_{i-1}
    4. B2>B1B_2 > B_1T2=T1T_2 = T_1BK1=BKB_{K-1} = B_KTK1<TKT_{K-1} < T_K
  • O 由一个大矩形 AA,挖去一个小矩形 BB 得到,这两个矩形的边都平行于坐标轴。设大矩形 AA 左下角的方格坐标为 (u,v)(u, v),长为 WW,宽为 HH,则小矩形 BB 满足左下角方格坐标为 (u+1,v+1)(u + 1, v + 1),长 W2W - 2,宽 H2H - 2。要求满足:
    1. W3W \ge 3H3H \ge 3
    2. u>RK+1u > R_K + 1
  • I33 个边平行于坐标轴的从下到上的实心矩形组成,从下到上依次标号为 1,2,31,2,3,第 ii 个矩形的左下角格子坐标设为 (Pi,Qi)(P_i , Q_i ),右上角格子坐标设为 (Gi,Hi)(G_i , H_i ),要求满足:
    1. PiGi,QiHiP_i \le G_i , Q_i \le H_i
    2. P1=P3>u+WP_1 = P_3 > u + WG1=G3G_1 = G_3
    3. Q1=H1=Q21,H2+1=Q3=H3Q_1 = H_1 = Q_2 - 1, H_2 + 1 = Q_3 = H_3
    4. P1<P2G2<G1P_1 < P_2 \le G_2 < G_1

下图是一个 N,O,I 的例子:

另外,所有画的图形均不允许超过纸张的边界。现在小 E 想要知道,他能画出的最大幸运度是多少。

输入格式

第一行包含两个正整数 nnmm ,分别表示矩阵的行数和列数。

接下来 nn 行,每行有 mm 个整数,第 i+1i + 1 行的第 jj 个数表示格子 (j,ni+1)(j, n - i + 1) 的幸运值。

输出格式

输出一个整数 TT,表示小 E 能够获得的最大幸运度。

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 

24
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


-20

提示

样例解释 1

样例解释 2

数据范围

测试点编号 nn mm 幸运值范围
1 =3=3 =12=12 [50,50][-50,50]
2
3
4
5 10\le10 20\le20
6
7
8
9 150\le150 500\le500 =1=1
10
11 80\le80 [200,200][-200,200]
12
13
14
15 150\le150 500\le500
16
17
18
19
20

对于所有的测试数据,保证 n3,m12n \ge 3,m \ge 12