#include <stdio.h>
#define dim 1000

int a[dim][dim],n,k,s1,s2,s3,colmin,colmax,liniemin,liniemax,total;

inline void coloana()
{
    int i;
    total+=s1;
    s2=s2-a[liniemax][colmin];
    s3=s3-a[liniemin][colmin];
    liniemin++;
    colmin++;
    //rebuild coloana
    s1=0;
    for (i=liniemin;i<=liniemax;i++)
        s1+=a[i][colmin];
}

inline void linie()
{
    int i;
    total+=s2;
    s1=s1-a[liniemax][colmin];
    s3=s3-a[liniemax][colmax];
    liniemax--;
    colmax--;
    //rebuild linie;
    s2=0;
    for (i=colmin;i<=colmax;i++)
        s2+=a[liniemax][i];
}

inline void diagonala()
{
    int i;
    total+=s3;
    s1=s1-a[liniemin][colmin];
    s2=s1-a[liniemax][colmax];
    liniemin++;
    colmax--;
    //rebuild diagonala
    s3=0;
    for (i=liniemin;i<=liniemax;i++)
        s3+=a[i][i];
}

void build()
{
    int i;
    for (i=0;i<k;i++)
    {
        if (s1>s2)  // col mai mare decat linia
        {
            if (s1>s3) //col e suma cea mai mare
                coloana();
            else       //diagonala e suma cea mai mare
                diagonala();

        }
        else        // linia mai mare decat col
        {
            if (s2>s3) //linia e suma cea mai mare
                linie();
            else        //diagonala e suma cea mai mare
                diagonala();
        }
    }
}

int main()
{
    int i,j;
    freopen("ferma2.in","r",stdin);
    freopen("ferma2.out","w",stdout);
    scanf("%d %d",&n,&k);
    for (i=0;i<n;i++)
        for (j=0;j<=i;j++)
        {
            scanf("%d",&a[i][j]);
            if (j==0)
                s1+=a[i][j]; //suma pe coloana
            if (i==n-1)
                s2+=a[i][j]; //suma pe linie
            if (i==j)
                s3+=a[i][j]; //suma pe diagonala
        }
    colmin=0,colmax=n-1,liniemin=0,liniemax=n-1;
    build();
    printf("%d\n",total);
    return 0;
}