/*
* poj3422 AC
* 网络流 最小费用最大流
* 图的模型
* 每个方格拆成两个节点u和v，用两条边连接，一条容量为1，费用为方格数字的相反数;
* 另一条边容量为k-1，费用为0。
* 每个方格的v节点与左边和下面方格的u节点相连，容量为k，费用为0。
* 创建源点s与汇点t，s与第一个方格的u节点相连，容量为k，费用为0。
* 最后一个方格的v节点与t相连，容量为k，费用为0。
* 每一条边均要创建其退边。
*
* 模板
* I 建图
* 采用邻接表，记录每一条边，边结点中记录边的起点与终点，边的剩余流量c，和该边的费用v。
* 同时建立这条边的退边，同样记录退边的起点与终点，边的剩余流量0，和改变的费用-v。
* 邻接表数组从零开始记录，前向边与退边相邻相邻，即前向边为i时，退边为i^1；同理，退边为
* i时，其前向边为i^1。非常精巧与方便，但记得把next，pre等数组赋初值为-1！
* II SPFA寻找费用最小边
* SPFA寻找图中费用最小的，从源点s到汇点t的路径，并用pre记录下路径。
* 除了要求路径的费用即权值最小，还要求边节点剩余流量大于0。
* 若dis[t]!=INF，则说明存在可以增广的路径，则可以增广。
* 直到找不到增广路径时，即已经找到最小费用最大流。
* III更新图中的剩余流量
* 在已经找出路径中找出剩余流量的最大值，然后沿着路径更新每一条前向边与退边的剩余流量。
* 并将路径上的费用相加。
* addcol();
* IV while(spfa())
* addcol();
*
* */
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define MAXN 5005
using namespace std;
int n,k;
struct NODE
{
int col,val,u,v;
}map[100000];
struct MAP
{
int val,u,v;
}m[52][52];
long ans;
int head[MAXN],next[100000],tot,pre[MAXN],dis[MAXN],s,t;
bool vis[MAXN];
void connect(int x,int y,int c,int val)
{
map[tot].val = val,map[tot].col = c,map[tot].u = x,map[tot].v= y;
next[tot] = head[x],head[x] = tot++;
map[tot].val = -val,map[tot].col = 0,map[tot].u = y,map[tot].v = x;
next[tot] = head[y],head[y] = tot++;
}
long spfa()
{
queue<int> que;
memset(vis,false,sizeof(vis));
memset(pre,-1,sizeof(pre));
memset(dis,-1,sizeof(dis));
que.push(s);
vis[s] = true,dis[s] = 0;
while(!que.empty())
{
int u = que.front();
que.pop();
vis[u] = false;
for(int i=head[u];i!=-1;i=next[i])
{
int v = map[i].v;
if(map[i].col>0 && (dis[v]==-1 || dis[v]>dis[u]+map[i].val))
{
dis[v] = dis[u]+map[i].val;
pre[v] = i;
if(!vis[v])
{
vis[v] = true;
que.push(v);
}
}
}
}
if(dis[t]!=-1) return true;
else return false;
}
void addcol()
{
int i,mi = 0xffffff;
for(i=pre[t];i!=-1;i=pre[map[i].u])
mi = min(mi,map[i].col);
for(i=pre[t];i!=-1;i=pre[map[i].u])
{
map[i].col -= mi,map[i^1].col += mi;
ans += mi*map[i].val;
}
}
int main()
{
scanf("%d%d",&n,&k);
int i,j;
for(t=0,i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&m[i][j].val);
m[i][j].val *= (-1);
m[i][j].u = t++;
m[i][j].v = t++;
}
s = t++;
memset(next,-1,sizeof(next));
memset(head,-1,sizeof(head));
tot = 0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
connect(m[i][j].u,m[i][j].v,1,m[i][j].val);
connect(m[i][j].u,m[i][j].v,k-1,0);
if(i+1<=n) connect(m[i][j].v,m[i+1][j].u,k,0);
if(j+1<=n) connect(m[i][j].v,m[i][j+1].u,k,0);
}
connect(s,m[1][1].u,k,0);
connect(m[n][n].v,t,k,0);
ans = 0;
while(spfa())
addcol();
printf("%ld\n",-ans);
return 0;
}