#include<bits/stdc++.h>
using namespace std;
long long n,k,a[105][105],dp[105][105][5050],ans;
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=1;i<=n;i++){//初始化 
		dp[n][i][0]=a[n][i]; 
		dp[n][i][1]=a[n][i]*3;
	}
	for(int i=n-1;i>=1;i--){//从下往上 
		for(int j=1;j<=i;j++){
			for(int z=0;z<=n-i+1;z++){
				if(z<=n-i)dp[i][j][z]=max(dp[i+1][j][z],dp[i+1][j+1][z])+a[i][j];//当该数不乘3 
				if(z>0)dp[i][j][z]=max(dp[i][j][z],max(dp[i+1][j][z-1],dp[i+1][j+1][z-1])+3*a[i][j]);//如果乘 
			}
		}
	}
	for(int i=1;i<=k;i++)ans=max(ans,dp[1][1][i]);
	cout<<ans<<endl;
	return 0;
}