题目描述

给定一个 $n\times n$ 的网格。

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

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

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

输入格式

第 $1$ 行 $2$ 个整数 $n,k$。

第 $2$ 到 $n+1$ 行，每行 $n$ 个整数。表示网格中每个格子里的捕鼠器个数。

输出格式

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

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

36

数据规模与约定

对于 $100\%$ 的数据，$2\le n\le 250$，$1\le k\le\frac{n}{2}$。