Problem C: 爱吃奶酪的肥老鼠

Problem C: 爱吃奶酪的肥老鼠

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 351  Solved: 91
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI家里来了一只肥老鼠!!!
它的活动区域在一个n*n的方格矩阵中,其中每个方格上都一些奶酪,肥老鼠很懒,当它在一个方格吃完奶酪的时候,他最多往上下左右其中一个方向直走k步去找下一块奶酪。肥老鼠也很饿,当它在一个方格吃完奶酪之后,他的下一个目标方格的奶酪必须比当前的奶酪大。现在肥老鼠从(0,0)出发,请问: 肥老鼠最多能吃到多少奶酪?

Input

输入包含多组测试用例。
对于每组测试用例,第一行包含两个数字n和k(1<=n,k<=100)。
接下来输入包含一个 n*n的方格矩阵(不超过10000)。
以一对 -1 -1结束所有输入。

Output

对于每组测试用例,输出肥老鼠能够吃到的最多奶酪数。

Sample Input

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

Sample Output

37