#include<iostream>
#include<cstring>
using namespace std;
long long n,k;
long long a[105][105];
long long dp[105][105][5055];
//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(dp,-0x3f,sizeof(dp));
	dp[1][1][0]=a[1][1];
	dp[1][1][1]=a[1][1]*3;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j-1][0])+a[i][j];
			for(int l=1;l<=k;l++){
				dp[i][j][l]=max(dp[i-1][j][l],dp[i-1][j-1][l])+a[i][j];
				dp[i][j][l]=max(dp[i][j][l],max(dp[i-1][j][l-1],dp[i-1][j-1][l-1])+a[i][j]*3);
				
			} 
		}
	}
	long long maxn=-1*0x3f3f3f3f3f3f3f3f;
	for(int j=1;j<=n;j++){
		for(int l=0;l<=k;l++){
			maxn=max(maxn,dp[n][j][k]);
		}
	}
	cout<<maxn;
	return 0;
}

只得了40分，考虑负数了