#include <bits/stdc++.h>
#define R(x) x = read()
#define ENDL push('\n');
#define SPACE push(' ');
#define int long long
using namespace std;
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c) {
	if(pp - pbuf == 1<<20)fwrite(pbuf, 1, 1<<20, stdout),pp = pbuf;
	*pp++ = c;
}
class io {public:~io() {fwrite(pbuf, 1, pp - pbuf, stdout);}} _;
inline void write(int x) {
	if (x<0)x=-x,push('-');
	int sta[35],top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while (x);
	while(top)push(sta[--top]^'0');
}
#ifndef LOCAL
	char buf[1<<23],*p1=buf,*p2=buf;
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
int n,k,s,t;
int id(int x,int y,int t){
	return (x-1)*n+y+t*n*n;
}
struct edge{
	int to,nxt,flow,cost;
}v[40010];
int len=1,fir[15010];
constexpr int inf=1e17;
void add(int x,int y,int f,int w){
	++len;
	v[len].to=y;
	v[len].flow=f;
	v[len].cost=w;
	v[len].nxt=fir[x];
	fir[x]=len;
}
int dis[15010],flow[15010],lst[15010],vis[15010];
bool spfa(){
	queue<int> q;
	q.push(s);
	memset(dis,0x3f3f3f3f,sizeof(dis));
	dis[s]=0;
	memset(flow,0x3f3f3f3f,sizeof(flow));
	memset(lst,-1,sizeof(lst));
//	memset(vis,0,sizeof(vis));
	while(!q.empty()){
		int u=q.front();
		vis[u]=0;
		q.pop();
		if(u==t)return 1;
		for(int i=fir[u];i;i=v[i].nxt){
			if(v[i].flow<=0)continue;
			if(dis[v[i].to]>dis[u]+v[i].cost){
				dis[v[i].to]=dis[u]+v[i].cost;
				flow[v[i].to]=min(flow[u],v[i].flow);
				lst[v[i].to]=i;
				if(!vis[v[i].to]){
					q.push(v[i].to);
					vis[v[i].to]=1;
				}
			}
		}
	}
	return lst[t]^(-1);
}
int ans;
void maxcost(){
	while(spfa()){
		int u=t;
		ans-=flow[t]*dis[t];
		while(u^s){
			v[lst[u]].flow-=flow[t];
			v[lst[u]^1].flow+=flow[t];
			u=v[lst[u]^1].to;
		}
	}
}
signed main(){
	R(n);R(k);
	s=id(n,n,1)+1;
	t=s+1;
	add(s,id(1,1,0),k,0);
	add(id(1,1,0),s,0,0);
	add(id(n,n,1),t,k,0);
	add(t,id(n,n,1),0,0);
	for(int i=1,x;i<=n;i++){
		for(int j=1;j<=n;j++){
			R(x);
			add(id(i,j,0),id(i,j,1),1,-x);
			add(id(i,j,1),id(i,j,0),0,x);
		}
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<=n;j++){
			add(id(i,j,1),id(i+1,j,0),inf,0);
			add(id(i+1,j,0),id(i,j,1),0,0);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<n;j++){
			add(id(i,j,1),id(i,j+1,0),inf,0);
			add(id(i,j+1,0),id(i,j,1),0,0);
		}
	}

	maxcost();
	write(ans);
    return 0;
}