#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 110, K = 5150;
signed main() {
    int n,k1;
    cin >> n >> k1;
    int a[N][N] = {};
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    }
    int dp[N][N][K];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                dp[i][j][j] = -3e9;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            for (int k = 0; k <= k1 && k <= i; k++) {
                if (k == 0) {
                    dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k]) + a[i][j];
                } else {
                    dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k]) + a[i][j];
                    dp[i][j][k] = max(dp[i][j][k], max(dp[i-1][j][k-1], dp[i-1][j-1][k-1]) + a[i][j] * 3);
                }
            }
        }
    }
    k1 = min(n,k1);
    int ans = -0x3f3f3f3f;
    for (int j = 1; j <= n; j++) {
        for (int k = 0; k <= k1; k++) {
            ans = max(dp[n][j][k],ans);
        }
    }
    cout << ans;
	return 0;
}