# include <cstdio>

const char *FIN = "ferma2.in", *FOU = "ferma2.out";
const int MAX = 1005;

int N, K, suma;
int V[MAX][MAX], L[MAX][MAX], C[MAX][MAX], D[MAX][MAX], dp[MAX][MAX];

inline void getmin (int &a, int b) {
    a = a < b ? a : b;
}

# define X (N - K)

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d %d", &N, &K);
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= i; ++j) {
            scanf ("%d", V[i] + j), suma += V[i][j];
            L[i][j] = V[i][j] + L[i][j - 1];
            C[i][j] = V[i][j] + C[i - 1][j];
            D[i][j] = V[i][j] + D[i - 1][j - 1];
        }
    for (int i = 1; i <= X; ++i)
        for (int j = 1; j <= i; ++j)
            dp[1][1] += V[i][j];
    int mini = dp[1][1];

    for (int i = 2; i <= K + 1; ++i) {
        dp[i][1] = dp[i - 1][1] - D[i + X - 2][X] + L[i + X - 1][X];
        getmin (mini, dp[i][1]);
        for (int j = 2; j <= i; ++j)
            getmin (mini, dp[i][j] = dp[i][j - 1] + D[i + X - 1][j + X - 1] - D[i - 1][j - 1] - C[i + X - 1][j - 1] + C[i - 1][j - 1]);
    }
    fprintf (fopen (FOU, "w"), "%d", suma - mini);
}