#include<bits/stdc++.h>
#define int long long
using namespace std;
int Read(); void Rite(int x);
const int maxn = 102;
const int maxm = 5003;
int n,k,a[maxn][maxn],ans(LONG_LONG_MIN);
int dp[maxn][maxn][maxm];
bool vis[maxn][maxn][maxm];
int DFS(int i,int j,int x){
	if(i == 0 || j == 0) return 0;
	if(vis[i][j][x]) return dp[i][j][x];
	vis[i][j][x] = 1;
	if(x) dp[i][j][x] = 
		max(DFS(i - 1,j,x - 1) + a[i][j] * 3,
			  DFS(i - 1,j - 1,x - 1) + a[i][j] * 3);
	dp[i][j][x] = 
	  max(dp[i][j][x],
		max(DFS(i - 1,j,x) + a[i][j],
			  DFS(i - 1,j - 1,x) + a[i][j]));
	ans = max(ans,dp[i][j][x]);
	return dp[i][j][x];
}
signed main(){
	memset(dp,-0x3f,sizeof(dp));
	n = Read(); k = Read();
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= i;++j)
			a[i][j] = Read();
	for(int i = 1;i <= n;++i)
		DFS(n,i,k);
	Rite(ans);
	return 0;
}
int Read(){
	char c(getchar());
	int x(0),f(1);
	while(c < '0' || c > '9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}
void Rite(int x){
	if(x < 0) putchar('-'),x = -x;
	if(x > 9) Rite(x / 10);
	putchar(x % 10 + '0');
}