#include <fstream>

using namespace std;

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

#define MAX_N 1010

int n, k, sol, tot;

int A[MAX_N][MAX_N], sum_d[MAX_N][MAX_N], sum_o[MAX_N][MAX_N], sum_v[MAX_N][MAX_N], ans[MAX_N][MAX_N];

int main() {

    f >> n >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++) {
            f >> A[i][j];
            tot += A[i][j];

            sum_d[i][j] = A[i][j] + sum_d[i - 1][j - 1];
            sum_o[i][j] = A[i][j] + sum_o[i][j - 1];
            sum_v[i][j] = A[i][j] + sum_v[i - 1][j];
        }

    for (int i = 1; i <= n - k; i++)
        ans[n][1] += sum_d[n][i];

    for (int i = n; i >= (n - k); i--)
        for (int j = 1; j <= i - (n - k) + 1; j++) {
            if (!(i == n && j == 1)) {
                if (j == 1) {
                    ans[i][j] = ans[i + 1][j];
                    ans[i][j] -= sum_o[i + 1][j + (n - k) - 1] - sum_o[i + 1][j - 1];
                    ans[i][j] += sum_d[i][j + (n - k) - 1] - sum_d[i - (n - k)][j - 1];
                }
                else {
                    ans[i][j] = ans[i][j - 1];
                    ans[i][j] -= sum_v[i][j - 1] - sum_v[i - (n - k)][j - 1];
                    ans[i][j] += sum_d[i][j + (n - k) - 1] - sum_d[i - (n - k)][j - 1];
                }
            }
        
            sol = (sol < tot - ans[i][j]) ? tot - ans[i][j] : sol;
        }

    g << sol;

    return 0;
}