#P2228. [HNOI2001] 洋洋吃蛋糕

[HNOI2001] 洋洋吃蛋糕

题目描述

洋洋是有名的“小馋猫”。他爱吃许多东西,但也有一些不爱吃的东西。一天,洋洋发现家中有一块刚烤好的长方形的蛋糕,而且蛋糕里放上了各种各样的东西,有爱吃的草莓,奶酪,也有不爱吃的核桃仁。这使得洋洋有一些为难,到底是吃还是不吃呢?这时,爷爷看出了洋洋的烦恼,然后说:你若能够遵守以下几条规则的话,蛋糕可以随便吃:

  1. 蛋糕的尺寸为 n×mn\times m,在吃之前,需先把蛋糕划分成 n×mn\times m 个单位蛋糕块,然后对每一个单位蛋糕块按照自己的喜好给其打分,分数越高表示越爱吃,反之则表示越不爱吃。这个分数为这一个单位蛋糕块的好吃程度值。

  2. 每一个单位蛋糕块要么全部被吃掉,要么不吃。

  3. 被吃掉的蛋糕块必须成长方形或正方形,是由一些单位蛋糕块组成的,且蛋糕块的两边必须和原来的大蛋糕块的两边平行。一块蛋糕块的好吃程度值就是所有组成这个蛋糕块的单位蛋糕块的分数之和。

  4. 被吃掉的蛋糕块的尺寸任意,且块数也任意。

  5. 为了保持蛋糕块的美观,所有被吃掉的蛋糕块在原来的大蛋糕块中的位置不能相邻,且不能重叠。如图 1 和图 2 的吃法是不允许的,而图 3 和图 4 的吃法是允许的。

  6. 所有被吃掉的蛋糕块的好吃程度值之和最大。

爷爷的话并没有消去洋洋的烦恼,因为他只能做好第一点,而不知如何选择蛋糕块。于是,洋洋请你帮忙选择蛋糕块,以使得所有被吃掉的蛋糕块的好吃程度值之和最大。

输入格式

第一行是两个整数 nnmm

以下 nn 行是一个 nnmm 列的矩阵,第 ii 行第 jj 列的整数表示单位蛋糕块 (i,j)(i,j) 的好吃程度值 cc

输出格式

只有一个数,即为最大的好吃程度值。

2 3                            
4 5 -2
-1 2 1

10

提示

数据规模与约定

对于 100%100\% 的数据,保证 1n2001\le n\le 2001m101\le m\le 10100c100-100\le c\le 100