#include <bits/stdc++.h>
using namespace std;

ifstream ci("ferma2.in");
ofstream cou("ferma2.out");

int v[1005][1005];
int sumln[1005][1005];
int sumcl[1005][1005];
int sumdg[1005][1005];

int n,k;
int sumt;

void citire(){
    ci>>n>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            ci>>v[i][j];
        }
    }
}

void initsm(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            sumt+=v[i][j];
            sumcl[i][j] = v[i][j]+sumcl[i-1][j];
            sumdg[i][j] = v[i][j]+sumdg[i-1][j-1];
            //cout<<i<<" "<<j<<" "<<v[i][j]<<" "<<sumln[i][j]<<" "<<sumcl[i][j]<<" "<<sumdg[i][j]<<"\n";
        }
        //cout<<"\n";
    }
    for(int i=n;i>=1;i--){
        for(int j=1;j<=n;j++){
            sumln[i][j] = v[i][j]+sumln[i+1][j]+sumln[i][j-1]-sumln[i+1][j-1];
            //cout<<i<<" "<<j<<" "<<sumln[i][j]<<"\n";
        }
    }
}

void rez(){
    int solmn=0;
    int smcol=0;
    int smdg=0;
    for(int i=0;i<=k;i++){
        smcol+=sumcl[n][i];
        smdg=0;
        for(int j=0;j<=k&&i+j<=k;j++){
            /// i pe coloana
            /// j pe diaonala
            int r=k-i-j;///coord liniiei
            int p=r;
            r=n-r+1;
            int smln=0;
            smln = sumln[r][n] - sumln[r][i];
            //pt diag adaug linia care nu mai e si diag urm
            if(j>0){
                smdg+=sumln[r-1][n] - sumln[r][n]-(sumln[r-1][n-j-p+1]-sumln[r][n-j-p+1]);
                smdg+=sumdg[r-1][n-p-j+1];
                smdg-=(sumln[j][i]-sumln[j+1][i]);
                //cout<<r-1<<" "<<n-p-j<<" "<<smdg<<"\n";
            }
            //cout<<"linii :"<<k-i-j<<" "<<r<<" "<<smln<<"\n";
            //cout<<"coloane :"<<i<<" "<<smcol<<"\n";
            //cout<<"diag :"<<j<<" "<<smdg<<"\n";
            //cout<<"\n";

            solmn=max(solmn,smln+smcol+smdg);

        }
        //cout<<"\n\n";
    }
    cou<<solmn;
}

int main()
{
    citire();
    initsm();
    rez();
    return 0;
}