#include <fstream>

using namespace std;

ifstream f("ferma2.in");
ofstream g("ferma2.out");

int n,k,i,p,j,a[10001][10001],ki,c,l,d;

int calcul() {
    int maxi,v;
    maxi=max(a[0][c],a[l][0]);
    maxi=max(maxi,a[n+1][n-d]);
    if (a[0][c]==maxi) {
        v=a[0][c];a[0][c]=0;
        for (int i=c;i<=n;i++) {
            a[i][0]-=a[i][c];
            a[n+1][n-i+c]-=a[i][c];
            a[i][c]=0;
        }
        c++;return v;
    }
    if (a[l][0]==maxi) {
        v=a[l][0];a[l][0]=0;
        for (int j=1;j<=l;j++) {
            a[0][j]-=a[l][j];
            a[n+1][n-(l-j)]-=a[l][j];
            a[l][j]=0;
        }
        l--;return v;
    }
    v=a[n+1][n-d];
    a[n+1][n-d]=0;
    int j=1;
    for (int i=d;i<=n && j<=n;i++,j++) {
        a[i][0]-=a[i][j];
        a[0][j]-=a[i][j];
        a[i][j]=0;
    }
    d++;
    return v;
}


int main () {
    f >> n >> k;
    for (i=1;i<=n;i++)
        for (j=1;j<=i;j++) {
            f >> a[i][j];
            a[i][0]+=a[i][j];
            a[0][j]+=a[i][j];
            a[n+1][n-(i-j)]+=a[i][j];
        }
    c=1;l=n;d=0;
    for (ki=1;ki<=k;ki++)
        p+=calcul();
    g << p << '\n';
    f.close();g.close();
    return 0;
}