#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=b;i>=a;--i)
using namespace std;
inline ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while (c<'0' || c>'9')
    {
        if (c=='-')  f=-1;
        c=getchar();
    }
    while (c>='0' && c<='9')
    {
        x=x*10+c-'0';
         c=getchar();
    }
    return x*f;
}
inline void print(ll x)
{
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
	return ;
}
const int N = 1e3;
const int M = 1e3;
ll d[N], q[N], hd, tl;
ll mf[N], vis[N], nxt[M << 1], to[M << 1], head[N], cnt = 1, c[M << 1], pre[N], cur[N], w[M << 1];
void add(int x, int y, ll cc, ll z)
{
	nxt[++cnt] = head[x];
	to[cnt] = y;
	c[cnt] = cc;
	w[cnt] = z;
	head[x] = cnt;
}
const ll inf = 1145141919810;
bool spfa(int st, int ed)
{
	//spfa不用初始化vis数组 
	memset(d, 0x3f, sizeof(d));
	memset(mf, 0, sizeof(mf));
	hd = tl = 0;
	vis[st] = 1;
	d[st] = 0;
	mf[st] = inf;
	q[++tl] = st;
	while(hd < tl)
	{
		int x = q[++hd];
		vis[x] = 0;
		for(int i = head[x]; i; i = nxt[i])
		{
			int y = to[i];
			if(d[y] > d[x] + w[i] && c[i])
			{
				d[y] = d[x] + w[i];
				mf[y] = min(mf[x], c[i]);
				pre[y] = i;
				if(!vis[y]) q[++tl] = y, vis[y] = 1;
			}
		}
	}
	return mf[ed] > 0;
}
int tot = 0;
void EK(int st, int ed)
{
	tot++;
	ll flow = 0, now = ed, cost = 0;
	while(spfa(st, ed))
	{
		now = ed;
		while(now != st)
		{
			int i = pre[now];
			c[i] -= mf[ed];
			c[i ^ 1] += mf[ed];
			now = to[i ^ 1];
		}
		flow += mf[ed];
		cost += mf[ed] * d[ed];//整条路都是 mf[ed] 所以只需要路径长度 *  流量即可 
	}
	cout << -cost << endl;
}
void ad(int x, int  y, ll c, ll w)
{
	add(x, y, c, w);
	add(y, x, 0, -w);
}
ll id[N][N];
ll a[N][N];
int main(){
	int n = read(), k = read();
	rep(i, 1, n)
		rep(j, 1, n)
			a[i][j] = -read(), id[i][j] = ++tot;
//	print(tot); puts("");
	int st = 2 * tot + 1;
	int ed = st + 1;
	ad(st, id[1][1], k, 0);
	ad(id[n][n] + tot, ed, k, 0);
	rep(i, 1, n)
		rep(j, 1, n)
			ad(id[i][j], id[i][j] + tot, 1, a[i][j]),
			ad(id[i][j], id[i][j] + tot, k - 1, 0);
	rep(i, 1, n - 1)
		rep(j, 1, n - 1)
			ad(id[i][j] + tot, id[i][j + 1], inf, 0), 
			ad(id[i][j] + tot, id[i + 1][j], inf, 0);
	rep(j, 1, n - 1)
		ad(id[n][j] + tot, id[n][j + 1], inf, 0);
	rep(i, 1, n - 1)
		ad(id[i][n] + tot, id[i + 1][n], inf, 0);
	EK(st, ed);
	return 0;
}