#include <stdio.h>
#define LMAX 1024

int x[LMAX][LMAX], S1[LMAX], S2[LMAX], S3[LMAX], c12[LMAX][LMAX], c13[LMAX][LMAX], c23[LMAX][LMAX];

int main ()
{
    int N, K, i, j, now, maxSum = 0, k;

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

    scanf ("%d%d", &N, &K);
    for (i = 1; i <= N; i ++)
        for (j = 1; j <= i; j ++)
            scanf ("%d", &x[i][j]);

    for (i = 1; i <= N; i ++)
        for (j = i; j <= N; j ++)
            S1[i] += x[j][i];
    for (i = 1; i <= N; i ++)
        for (j = 1; j <= N - i + 1; j ++)
            S2[i] += x[i + j - 1][j];
    for (i = 1; i <= N; i ++)
        for (j = 1; j <= N - i + 1; j ++)
            S3[i] += x[N - i + 1][j];

    for (i = 1; i <= N; i ++)
        for (j = 1; j <= i; j ++)
        {
            if (i - j + 1 > 0)
            {
                c12[j][i - j + 1] += x[i][j];
                c23[i - j + 1][N - i + 1] += x[i][j];
            }
            c13[j][N - i + 1] += x[i][j];
        }

    for (i = 1; i <= N; i ++)
        S1[i] += S1[i - 1], S2[i] += S2[i - 1], S3[i] += S3[i - 1];

    for (i = 1; i <= N; i ++)
        for (j = 1; j <= N; j ++)
        {
            if (i == 1)
            {
                c12[i][j] += c12[1][j - 1];
                c13[i][j] += c13[1][j - 1];
                c23[i][j] += c23[1][j - 1];
            }
            if (j == 1)
            {
                c12[i][j] += c12[i - 1][1];
                c13[i][j] += c13[i - 1][1];
                c23[i][j] += c23[i - 1][1];

            }
            c12[i][j] += c12[i - 1][j - 1];
            c13[i][j] += c13[i - 1][j - 1];
            c23[i][j] += c23[i - 1][j - 1];
        }

    for (i = 0; i <= K; i ++)
        for (j = 0; j <= K; j ++)
        {
            k = K - i - j;
            if (k < 0)
                continue;
            now = S1[i] + S2[j] + S3[k] - c12[i][j] - c13[i][k] - c23[j][k];
            if (now > maxSum)
                maxSum = now;
        }

    printf ("%d", maxSum);
    return 0;
}