#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=5050;
const int M=N*6;
const int INF=0x3f3f3f;
int mp[58][58];
struct node{
   int u,v,flow,cost,next;
}e[M];
int tot,head[N],pre[N],C[N],F[N],V[N],n,m;
void add(int u,int v,int flow,int cost){
   e[tot].u=u;e[tot].v=v;e[tot].flow=flow;e[tot].cost=cost;e[tot].next=head[u];head[u]=tot++;
   e[tot].u=v;e[tot].v=u;e[tot].flow=0;e[tot].cost=-cost;e[tot].next=head[v];head[v]=tot++;
}
int SPFA(int s,int t){
    memset(pre,-1,sizeof(pre));
    for(int i=1;i<=t+1;++i) F[i]=0,C[i]=INF,V[i]=0;
    queue<int>Q;
    Q.push(s);
    C[0]=0,F[0]=INF,V[0]=1;
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        V[u]=0;
        for(int i=head[u];i+1;i=e[i].next){
            int v=e[i].v,f=e[i].flow,c=e[i].cost;
            if(f>0&&C[v]>C[u]+c) {
                C[v]=C[u]+c;
                pre[v]=i;
                F[v]=min(f,F[u]);
                if(!V[v]) V[v]=1,Q.push(v);
            }
        }
    }
    return F[t];
}
int MCMF(int s,int t){
    int ans=0,temp;
    while(temp=SPFA(s,t)){
        for(int i=pre[t];i+1;i=pre[e[i].u]) {
            ans+=temp*e[i].cost;
            e[i].flow-=temp;
            e[i^1].flow+=temp;
        }
    }
    return ans;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(!m) {puts("0");continue;}
        memset(head,-1,sizeof(head));
        tot=0;
        for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) scanf("%d",&mp[i][j]);
        add(0,1,m,0);
        add(2*n*n,2*n*n+1,m,0);
        for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) {
            if(i<n) add((i-1)*n+j+n*n,i*n+j,m,0);
            if(j<n) add((i-1)*n+j+n*n,(i-1)*n+j+1,m,0);
        }
        for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) add((i-1)*n+j,(i-1)*n+j+n*n,1,-mp[i][j]);
        for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) add((i-1)*n+j,(i-1)*n+j+n*n,m-1,0);
        printf("%d\n",-MCMF(0,2*n*n+1));
    }
}