#include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <queue>

 using namespace std;

 const int INF = <<;

 const int N=;

 int Map[][],dis[N];

 int head[N],pre[N];

 bool vis[N];

 int cnt = ;

 int ans = ;

 int n;

 struct node

 {

     int u,v,c,f;

     int next;

 } edge[N];

 void add(int u,int v,int c,int f)

 {

     edge[cnt].u = u;

     edge[cnt].v = v;

     edge[cnt].c = c;

     edge[cnt].f = f;

     edge[cnt].next = head[u];

     head[u] = cnt++;

     edge[cnt].u = v;

     edge[cnt].v = u;

     edge[cnt].c = -c;

     edge[cnt].f = ;

     edge[cnt].next = head[v];

     head[v] = cnt++;

 }

 int spfa()

 {

     for (int i = ; i <= n*n*+; i++)

     {

         dis[i] = INF;

         pre[i] = -;

         vis[i] = false;

     }

     dis[n*n*] = ;

     queue<int>q;

     q.push(n*n*);

     vis[n*n*] = true;

     while(!q.empty())

     {

         int u = q.front();

         vis[u] = false;

         q.pop();

         for (int j = head[u]; j!=-; j=edge[j].next)

         {

             if (edge[j].f > &&dis[edge[j].v] > dis[u]+ edge[j].c)

             {

                 pre[edge[j].v] = j;

                 dis[edge[j].v] = dis[u]+ edge[j].c;

                 if (!vis[edge[j].v])

                 {

                     q.push(edge[j].v);

                     vis[edge[j].v] = true;

                 }

             }

         }

     }

     if (pre[n*n*+]==-)

         return ;

     return ;

 }

 void MCMF()

 {

     while(spfa())

     {

         int Minflow = INF;

         int j = pre[n*n*+];

         while(j!=-)

         {

             Minflow = min(Minflow,edge[j].f);

             j = pre[edge[j].u];

         }

         j = pre[n*n*+];

         while(j!=-)

         {

             edge[j].f-=Minflow;

             edge[j^].f+=Minflow;

             ans+=Minflow*edge[j].c;

             j = pre[edge[j].u];

         }

     }

 }

 int main()

 {

     int k;

     scanf("%d%d",&n,&k);

     memset(Map,,sizeof(Map));

     memset(head,-,sizeof(head));

     for (int i = ; i <= n; i++)

     {

         for (int j = ; j <= n; j++)

         {

             scanf("%d",&Map[i][j]);

         }

     }

     for (int i = ; i <= n; i++)//拆点

     {

         for (int j = ; j <= n; j++)

         {

             int u = (i-)*n+j-;

             add(*u,*u+,-Map[i][j],);//加边

             add(*u,*u+,,k-);

         }

     }

     for (int i = ; i <= n; i++)//向右加边

     {

         for (int j = ; j < n; j++)

         {

             int u = (i-)*n+j-;

             add(*u+,(u+)*,,k);

         }

     }

     for (int i = ; i < n; i++)//向下加边

     {

         for (int j = ; j <= n; j++)

         {

             int u = (i-)*n+j-;

             add(*u+,(u+n)*,,k);

         }

     }

     add(n*n*,,,k);//加源点

     add(n*n*-,n*n*+,,k);//加终点

     MCMF();

     printf("%d\n",-ans);

     return ;

 }