logo AlgoBeat OnlineJudge
登录 注册

#103087. [BZOJ 3087] Coci2009 misolovke

内存限制:128 MiB 时间限制:40000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定一个 的网格。

每个格子里至少会有一个捕鼠器,并且已知每个格子里的捕鼠器个数。现在需要在每一行中选取恰好 个连续的格子,把里面的捕鼠器全部拿走,并且需要满足老鼠不能从网格最左边到网格最右边也不能从网格最上面到网格最下面。

老鼠行走的方向是上下左右四个方向,且只能经过没有捕鼠器的格子。

求拿走捕鼠器个数的最大值。

输入格式

个整数

行,每行 个整数。表示网格中每个格子里的捕鼠器个数。

输出格式

仅一个整数,表示拿走捕鼠器个数的最大值。

样例

样例输入 #1

4 2
5 5 1 1
1 5 5 1
1 1 5 5
5 5 1 1

样例输出 #1

36

数据范围与提示

对于 的数据,