logo AlgoBeat OnlineJudge
登录 注册

#200392. [NOI2013] 书法家

内存限制:500 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

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

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

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

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

  • N 由若干()个边平行于坐标轴的矩形组成,设由 个矩形组成(标号 ),第 个矩形的左下角方格坐标设为 ,右上角坐标设为 ,要求满足:
    1. 对任意 ,有
    2. 对任意 ,有
  • O 由一个大矩形 ,挖去一个小矩形 得到,这两个矩形的边都平行于坐标轴。设大矩形 左下角的方格坐标为 ,长为 ,宽为 ,则小矩形 满足左下角方格坐标为 ,长 ,宽 。要求满足:
  • I 个边平行于坐标轴的从下到上的实心矩形组成,从下到上依次标号为 ,第 个矩形的左下角格子坐标设为 ,右上角格子坐标设为 ,要求满足:

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

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

输入格式

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

接下来 行,每行有 个整数,第 行的第 个数表示格子 的幸运值。

输出格式

输出一个整数 ,表示小 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

样例解释 2

数据范围

::cute-table{tuack}

测试点编号 幸运值范围
1
2 ^ ^
3
4
5
6 ^
7
8
9
10 ^
11
12 ^ ^
13
14
15
16 ^
17
18
19
20

对于所有的测试数据,保证