#include <fstream>

using namespace std;

const int N=1005;

ifstream fin("ferma2.in");
ofstream fout("ferma2.out");

int lin[N], col[N], diag[N], b[N][N], c[N][N], drept[N][N], inter1[N][N], inter2[N][N];

void afis(int n)
{
    int i;
    for(i=1;i<=n;i++) fout<<lin[i]<<" "; fout<<"\n";
    for(i=1;i<=n;i++) fout<<col[i]<<" "; fout<<"\n";
    for(i=1;i<=n;i++) fout<<diag[i]<<" "; fout<<"\n";
}

int main()
{
    int n, k, i, j, d, x, sol=0;
    fin>>n>>k;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=i;j++)
        {
            fin>>x;
            lin[n-i+1]+=x;
            col[j]+=x;
            diag[i-j+1]+=x;
            b[i][j]=b[i-1][j]+x;
            c[i][j]=c[i][j-1]+x;
            drept[i][j]=x+drept[i-1][j]+drept[i][j-1]-drept[i-1][j-1];
        }
    }
    for(i=1;i<=n;i++)
    {
        lin[i]+=lin[i-1];
        col[i]+=col[i-1];
        diag[i]+=diag[i-1];
    }
    //afis(n);
    for(i=1;i<=k;i++)
    {
        for(j=1;i+j<=k;j++)
        {
            inter1[i][j]=inter1[i-1][j]+b[i+j-1][i];
            inter2[i][j]=inter2[i-1][j]+c[n-i+1][n-i+1]-c[n-i+1][n-i+1-j];
            //fout<<inter2[i][j]<<" ";
        }
        //fout<<"\n";
    }
    for(i=0;i<=k;i++)
    {
        for(j=0;j+i<=k;j++)
        {
            d=k-i-j;
            x=lin[i]+col[j]+diag[d]-inter1[j][d]-inter2[i][d]-(drept[n][j]-drept[n][0]-drept[n-i][j]+drept[n-i][0]);
            sol=max(sol, x);
            //fout<<x<<" ";
        }
        //fout<<"\n";
    }
    fout<<sol;
    fin.close();
    fout.close();
}