题目描述

硕鼠在一个城市储存了一些奶酪。城市可以被认为是一个n*n的正方形网格:每个网格位置被标记为(p，q ),其中0 <= p < n，0 <= q < n。在每个网格位置，硕鼠在一个洞里藏了0到100块奶酪。现在他要享受他最喜欢的食物了。 硕鼠从位置(0，0)开始。他在原地吃完奶酪，然后水平或垂直地跑向另一个地方。问题是，有一只名叫黑仔的猫坐在他的洞附近，每次他都可以在被黑仔抓住之前跑最多k个位置进洞。更糟糕的是，在一个地方吃完奶酪后，硕鼠变得更胖了。因此，为了为下一次跑步获得足够的能量，他必须跑到一个比当前洞有更多奶酪块的地方。 给定n、k和每个网格位置的奶酪块数量，计算硕鼠在无法移动之前可以吃的奶酪的最大数量。

输入格式

有多个测试数据。每个测试数据包括 第一行包含两个整数:n和k($1 \le n,k \le 100$)
接下来n行，每一行有n个数字:第一行包含位置(0，0) (0，1)..(0，n-1)处奶酪块的数量.；下一行包含位置(1，0)、(1，1)，...(1，n-1)处奶酪块的数量，以此类推。 输入以一对-1结束。

输出格式

对于一行中的每个测试用例输出，给出所收集的奶酪块数量的单个整数。

3 1
1 2 5
10 11 6
12 12 7
-1 -1

37

提示