#include<iostream>
#include<cstring>
using namespace std;
long long n,k;
long long a[105][105];
long long dp1[105][5055];
long long dp2[105][5055];//dp[j][k]走到第j列，用了次變大機會的最大得分 
//dp[i][j][k]走到(i,j),用了k次變大機會的最大得分 
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
		}
	}
	memset(dp1,-0x3f,sizeof(dp1));
	memset(dp2,-0x3f,sizeof(dp2));
	dp1[1][0]=a[1][1];
	dp1[1][1]=a[1][1]*3;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			dp2[j][0]=max(dp1[j][0],dp1[j-1][0])+a[i][j];
			for(int l=1;l<=k;l++){
				dp2[j][l]=max(dp1[j][l],dp1[j-1][l])+a[i][j];
				dp2[j][l]=max(dp2[j][l],max(dp1[j][l-1],dp1[j-1][l-1])+a[i][j]*3);
				
			} 
		}
		memcpy(dp1,dp2,sizeof(dp2));
		memset(dp2,-0x3f,sizeof(dp2));
	}
	long long maxn=-1*0x3f3f3f3f3f3f3f3f;
	for(int j=1;j<=n;j++){
		for(int l=0;l<=k;l++){
			maxn=max(maxn,dp1[j][k]);
		}
	}
	cout<<maxn;
	return 0;
}

考虑复数了，还是40分