1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef unsigned int ui;
4 typedef long long ll;
5 typedef unsigned long long ull;
6 #define pf printf
7 #define prime1 1e9+7
8 #define prime2 1e9+9
9 #define scand(x) scanf("%llf",&x)
10 #define f(i,a,b) for(int i=a;i<=b;i++)
11 #define scan(a) scanf("%d",&a)
12 #define dbg(args) cout<<#args<<":"<<args<<endl;
13 #define pb(i) push_back(i)
14 #define ppb(x) pop_back(x)
15 #define maxn 1005
16 int n,k,t;
17 int Map[maxn][maxn],dp[maxn][maxn];
18 int dir[][2]={{0,1},{0,-1},{-1,0},{1,0}};
19 bool ok(int x,int y)
20 {
21 if(x<0||x>=n||y<0||y>=n)return false;
22 return true;
23 }
24 int dfs(int x,int y)
25 {
26 if(dp[x][y])return dp[x][y];
27 int temp=0;
28 int M=0;
29 f(i,0,3)
30 f(j,1,k)
31 {
32 int xx=x+dir[i][0]*j;
33 int yy=y+dir[i][1]*j;
34 if(ok(xx,yy)&&Map[xx][yy]>Map[x][y])
35 {
36 temp=dfs(xx,yy);
37 if(temp>dp[xx][yy])dp[xx][yy]=temp;
38 if(dp[xx][yy]>M)M=dp[xx][yy];
39 }
40 }
41
42 return dp[x][y]=Map[x][y]+M;
43 }
44 int main()
45 {
46 std::ios::sync_with_stdio(false);
47 while(scanf("%d%d",&n,&k)==2&&!(k==-1&&n==-1))
48 {
49 memset(dp,0,sizeof(dp));
50 f(i,0,n-1)
51 f(j,0,n-1)
52 {
53 scan(Map[i][j]);
54 }
55 dp[0][0]=dfs(0,0);
56 pf("%d
",dp[0][0]);
57 }
58 }
