$f_{i,j,k,0/1}$ 表示 $(1,1)\to(i,j)$，共使用了 $k$ 次三倍经验，且在 $(i,j)$ 是否使用了。

#include <bits/stdc++.h>
#define int long long
using lint = long long;
const int N = 110, M = N * N;

int n, K;
lint ans, a[N][N], f[2][N][M][2];

void input() {
  std::cin >> n >> K;
  if (K > n) K = n;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
      std::cin >> a[i][j];
    }
  }
}

void dp() {
  memset(f, -0x3f, sizeof(f));
  memset(f[0], 0, sizeof(f[0]));
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
      for (int k = 0; k <= K; ++k) {
        f[i & 1][j][k][0] = std::max({f[i - 1 & 1][j][k][0], f[i - 1 & 1][j][k][1], f[i - 1 & 1][j - 1][k][0], f[i - 1 & 1][j - 1][k][1]}) + a[i][j];
        if (k) f[i & 1][j][k][1] = std::max({f[i - 1 & 1][j][k - 1][0], f[i - 1 & 1][j][k - 1][1], f[i - 1 & 1][j - 1][k - 1][0], f[i - 1 & 1][j - 1][k - 1][1]}) + 3 * a[i][j];
      }
    }
  }
}

void output() {
  for (int j = 1; j <= n; ++j) {
    for (int k = 0; k <= K; ++k) {
      ans = std::max({ans, f[n & 1][j][k][0], f[n & 1][j][k][1]});
    }
  }
  std::cout << ans << std::endl;
}

signed main() {
  std::cin.tie(0)->sync_with_stdio(0);
  input();
  dp();
  output();
  return 0;
}