#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;}
    else if(k == n - 1){
        int Min = 2000000000;
        for(int i = 1; i <= n ; ++i)
            for(int j = 1; j <= i ; ++j)
                if(a[i][j] < Min) Min = a[i][j];
        printf("%d", Sum - Min);
        return 0;
    }
    int Min = 2000000000;
    for(int i = 1; i <= k + 1; ++i){
        for(int j = 1; j <= i ; ++j){
            int Sol = l[i + n - k - 1][j + n - k - 1] - l[i + n - k - 1][j - 1] + c[i + n - k - 1][j] - c[i - 1][j] + d[i + n - k - 2][j + n - k - 2] - d[i][j] - a[i + n - k - 1][j];
            if(Sol < Min)
                Min = Sol;
        }
    }
    printf("%d", Sum - Min);
    return 0;
}