#5和后面的测试点WA了（40分）

#include <bits/stdc++.h>
#define MAXN 105
#define INF -9187201950435737472
using namespace std;
typedef long long LL;
int w[MAXN][MAXN];
LL f[MAXN][MAXN][5055];
int main(int argc, const char * argv[]) {
    // insert code here...
    int n, k;
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> w[i][j];
        }
    }
    memset(f, 128, sizeof(f));
    f[1][1][0] = w[1][1];
    f[1][1][1] = w[1][1] * 3;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            for (int l = 0; l <= k && l <= i; l++) {
                f[i][j][l] = max(f[i-1][j][l], f[i-1][j-1][l]) + w[i][j];
                if (l != 0) {
                    f[i][j][l] = max(max(f[i][j][l], f[i-1][j][l-1] + w[i][j] * 3), f[i-1][j-1][l-1] + w[i][j] * 3);
                }
            }
        }
    }
    long long ans = INF;
    k = min(k, n);
    for (int i = 1; i <= n; i++) {
        ans = max(ans, f[n][i][k]);
    }
    cout << ans << endl;
    return 0;
}