#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
const int maxn=5100,inf=1000000000;
struct poii{int too,pre,c,f,cf,v;}e[1000010];
int h[maxn],dist[maxn],pre[maxn],last[maxn];
int sum,ans,n,m,tot,x,k,z;
bool v[maxn];
using namespace std;
void add(int x,int y,int c,int v)
{
    e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;
    e[tot].c=e[tot].cf=c;e[tot].v=v;
    e[++tot].too=x;e[tot].pre=last[y];last[y]=tot;e[tot].v=-v;
}
void read(int &k)
{
    k=0;int f=1;char c=getchar();
    while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar();
    while(c<=‘9‘&&c>=‘0‘)k=k*10+c-‘0‘,c=getchar();
    k*=f;
}
void spfa(int s)
{
    int front=0,rear=1;
    for(int i=0;i<=sum;i++)dist[i]=-inf,v[i]=0,pre[i]=-1;
    dist[s]=0;v[s]=1;h[1]=s;
    while(front!=rear)
    {
        if(front>maxn)front=-1;
        int now=h[++front];
        for(int i=last[now],too=e[i].too;i;i=e[i].pre,too=e[i].too)
        if(e[i].cf)
        if(dist[too]<dist[now]+e[i].v)
        {
            dist[too]=dist[now]+e[i].v;pre[too]=i;
            if(!v[too])v[too]=1,rear>maxn&&(rear=-1),h[++rear]=too;
        }
        v[now]=0;
    }
}
void ford(int s,int t)
{
    spfa(s);
    while(pre[t]!=-1)
    {
        int mincf=inf,cnt=0;;
        for(int i=pre[t];i!=-1;i=pre[e[i^1].too])
        mincf=min(mincf,e[i].cf);
        ans+=mincf*dist[t];
        for(int i=pre[t];i!=-1;i=pre[e[i^1].too])
        {
            e[i].f+=mincf;e[i^1].f=-e[i].f;
            e[i].cf-=mincf;e[i^1].cf+=mincf;
        }
        spfa(s);
    }
}
int num(int x,int y){return (x-1)*n+y;}
int main()
{
    tot=1;
    read(n);read(k);sum=2*n*n+1;
    add(0,1,k,0);add(2*n*n,sum,k,0);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
        read(z);int x=num(i,j);
        add(x,x+n*n,1,z);
        add(x,x+n*n,inf,0);
        if(i+1<=n)add(x+n*n,num(i+1,j),inf,0);
        if(j+1<=n)add(x+n*n,num(i,j+1),inf,0);
    }
    ford(0,sum);
    printf("%d\n",ans);
}