#include <bits/stdc++.h>
using namespace std;
long long a[105][105],dp1[105][105],dp2[105][105],n,k; 
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)
{
	for(int j=1;j<=i;j++)
	{
	  cin>>a[i][j];	
	} 
}
if(k>n) k=n;
for(int i=0;i<=n+1;i++)
{
	dp1[i][0]=-1e18;
	dp2[i][0]=-1e18; 
}
for(int i=1;i<=n;i++)
{
	for(int j=1;j<=i;j++)
	{
	  dp1[i][j]=max(dp1[i-1][j-1],dp1[i-1][j])+a[i][j];	
	} 
}
for(int h=1;h<=k;h++)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
		 dp2[i][j]=max((max(dp1[i-1][j-1],dp1[i-1][j])+a[i][j]*3),
		      (max(dp2[i-1][j-1],dp2[i-1][j])+a[i][j]));
		} 
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
		  dp1[i][j]=dp2[i][j];	
		} 
	}	
}

long long ans=-1e18;
for(int j=1;j<=n;j++)
{
	ans=max(ans,dp1[n][j]);
}
cout<<ans;
	return 0;
}