#include<cstdio>

const int N = 1002;
const int M = 5;

int n, k, a[N][N], d[N][M], st1[N][M], st2[N][M], jos1[N][M], jos2[N][M], sl[N][N], sc[N][N], sd[N][N];

void citire() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            scanf("%d", &a[i][j]);
}

void sumepartiale() {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j) {
            sl[i][j] = sl[i][j - 1] + a[i][j];
            sc[i][j] = sc[i - 1][j] + a[i][j];
            sd[i][j] = sd[i - 1][j - 1] + a[i][j];
        }
}

inline int pozmax(int lin) {
    int m = -1, poz;
    for (int i = 0; i < 3; ++i)
        if (d[lin][i] > m) {
            m = d[lin][i];
            poz = i;
        }

    return poz;
}

int suma(int lin, int poz, int luat) {
    int x1 = st1[lin][poz], y1 = st2[lin][poz], x2 = jos1[lin][poz], y2 = jos2[lin][poz];

    if (luat == 0)
        return sl[x2][y2] - sl[x2][y1 - 1];

    if (luat == 1)
        return sc[x2][y1] - sc[x1 - 1][y1];

    return sd[x2][y2] - sd[x1 - 1][y1 - 1];
}

void rez() {
    // 0 - linia ; 1 - coloana ; 2 - diagonala

    for (int i = 0; i < 3; ++i) {
        st1[0][i] = 1;
        st2[0][i] = 1;
        jos1[0][i] = n;
        jos2[0][i] = n;
    }

    for (int i = 1; i <= k; ++i) {
        int poz = pozmax(i - 1);

        d[i][0] = d[i - 1][poz] + suma(i - 1, poz, 0);
        st1[i][0] = st1[i - 1][poz];
        st2[i][0] = st2[i - 1][poz];
        jos1[i][0] = jos1[i - 1][poz] - 1;
        jos2[i][0] = jos2[i - 1][poz] - 1;
        printf("%d linie %d\n", i, d[i - 1][poz] + suma(i - 1, poz, 0));
        printf("%d %d  %d %d\n", st1[i][0], st2[i][0], jos1[i][0], jos2[i][0]);

        d[i][1] = d[i - 1][poz] + suma(i - 1, poz, 1);
        st1[i][1] = st1[i - 1][poz] + 1;
        st2[i][1] = st2[i - 1][poz] + 1;
        jos1[i][1] = jos1[i - 1][poz];
        jos2[i][1] = jos2[i - 1][poz];
        printf("%d coloana %d\n", i, d[i - 1][poz] + suma(i - 1, poz, 1));
        printf("%d %d  %d %d\n", st1[i][1], st2[i][1], jos1[i][1], jos2[i][1]);

        d[i][2] = d[i - 1][poz] + suma(i - 1, poz, 2);
        st1[i][2] = st1[i - 1][poz] + 1;
        st2[i][2] = st2[i - 1][poz];
        jos1[i][2] = jos1[i - 1][poz];
        jos2[i][2] = jos2[i - 1][poz] - 1;
        printf("%d diagonala %d\n", i, d[i - 1][poz] + suma(i - 1, poz, 2));
        printf("%d %d  %d %d\n", st1[i][2], st2[i][2], jos1[i][2], jos2[i][2]);
    }

    int poz = pozmax(k);

    printf("%d\n", d[k][poz]);
}

int main() {
    freopen("ferma2.in", "r", stdin);
    freopen("ferma2.out", "w", stdout);;

    citire();

    sumepartiale();

    rez();

    return 0;
}