Coci2009 misolovke

时间限制:40s      空间限制:128MB

题目描述

[misolovke]
给定一个 N*N 的网格.
每个格子里至少会有一个捕鼠器, 并且已知每个格子里的捕鼠器个数.现在需要在 每一行 中选取恰好 K 个连续的格子, 把里面的捕鼠器全部拿走, 并且需要满足

 老鼠不能 从网格最左边到网格最右边
 也不能 从网格最上面到网格最下面
 老鼠行走的方向是 上下左右 4个方向
 老鼠只能经过没有捕鼠器的格子
求拿走捕鼠器个数的最大值


输入格式


    第1行: 2 个整数 N, K (2 <= N <= 250, 1 <= K <= N/2)
    第2..N+1行: 每行 N 个整数. 表示网格中每个格子里的捕鼠器个数.


输出格式


    第1行: 仅一个整数, 表示拿走捕鼠器个数的最大值


样例输入

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

样例输出

36

提示

没有写明提示


题目来源

没有写明来源