#include <cstdio>
#define MAXN 1000

int a[MAXN+1][MAXN+1], so[MAXN+1][MAXN+1], sv[MAXN+1][MAXN+1], sd[MAXN+1][MAXN+1];
inline int min2(int a, int b){
    return (a<b ? a : b);
}

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

    int i, j, n, k, lat, s=0, smin, si=0;

    scanf("%d%d", &n, &k);
    lat = n-k;

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

    for(i=1;i<=n; ++i)
        for(j=1; j<=i; ++j){
            so[i][j] = so[i][j-1] + a[i][j];
            sv[i][j] = sv[i-1][j] + a[i][j];
            sd[i][j] = sd[i-1][j-1] + a[i][j];
        }

    if(lat == 0){
        printf("%d", s);
        return 0;
    }

    for(i=1; i<=lat; ++i)
        si += so[i][i];

    a[lat][lat] = smin = si;
    for(i=lat+1; i<=n; ++i)
    {
        a[i][lat] = a[i-1][lat] + so[i][lat] - sd[i-1][lat];
        smin = min2(smin, a[i][lat]);
        for(j=lat+1; j<=i; ++j){
            a[i][j] = a[i][j-1] + sd[i][j] - sd[i-lat][j-lat] - (sv[i][j-lat] - sv[i-lat][j-lat]);
            smin = min2(smin, a[i][j]);
        }
    }
    printf("%d", s - smin);

    return 0;
}