#include <cstdio>
using namespace std;

int n, k, a[1001][1001], l[1001][1001], c[1001][1001], d[1001][1001];
int main()
{
    freopen("ferma2.in", "r", stdin);
    freopen("ferma2.out", "w", stdout);
    scanf("%d%d", &n, &k);
    int Sum = 0;
    for(int i = 1; i <= n ; ++i){
        for(int j = 1; j <= i ; ++j){
            scanf("%d", &a[i][j]), Sum += a[i][j];
            l[i][j] = l[i][j - 1] + a[i][j];
            c[i][j] = c[i - 1][j] + a[i][j];
            d[i][j] = d[i - 1][j - 1] + a[i][j];
        }
    }
    if(k == n) {printf("%d", Sum); return 0;}
    else if(k == 0) {printf("%d", 0); return 0;}
    int Smin = 0;
    for(int i = 1; i <= n - k ; ++i)
        Smin = Smin + l[i][i];
    int Min = Smin;
    for(int i = 2; i <= k + 1 ; ++i){
        Smin = Smin + l[i + n - k - 1][n - k] - d[i + n - k - 2][n - k];
        if(Smin < Min) Min = Smin;
        for(int j = 2; j <= i ; ++j){
            Smin = Smin - (c[i + n - k - 1][j - 1] - c[i - 1][j - 1]) + (d[i + n - k - 1][j + n - k - 1] - d[i - 1][j - 1]);
            if(Smin < Min) Min = Smin;
        }
    }
    printf("%d", Sum - Min);
    return 0;
}