#include<bits/stdc++.h>
using namespace std;
const int N = 1e2+10;
const long long inf = 1e18;
long long  n,k;
long long  a[N][N];
// dp[i][j][k],到达a[i][j]乘了k次3的最大值
long long  dp[N][N][N]; 
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
		}
	}
	// 初始化
	for(int i=0;i<=n;i++){
		for(int j=0;j<=i;j++){
			for(int l=0;l<=k;l++){
				dp[i][j][l] = -inf; // 赋值为极小值
			}
		}
	}
	// 初始化
	dp[1][1][0] = a[1][1];
	dp[1][1][1] = a[1][1]*3;
	// 开始dp
	if(k>n) k=n;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			// 先将 k==0的情况解决了
			dp[i][j][0]=max(dp[i-1][j][0]+a[i][j],dp[i-1][j-1][0]+a[i][j]);
			for(long long l=1;l<=min(k,l);l++){
				dp[i][j][l] = max(dp[i][j][l],dp[i-1][j][l]+a[i][j]);
				dp[i][j][l] = max(dp[i][j][l],dp[i-1][j-1][l]+a[i][j]);
				dp[i][j][l] = max(dp[i][j][l],dp[i-1][j][l-1]+a[i][j]*3);
				dp[i][j][l] = max(dp[i][j][l],dp[i-1][j-1][l-1]+a[i][j]*3);
			}
		}
	}
	long long  ans = -inf;
	for(int j=1;j<=n;j++){
		for(int l=0;l<=k;l++){
			ans = max(ans, dp[n][j][l]);
		}
	}
	cout<<ans;
	return 0;
}