#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,K;
ll a[105][105],dp[105][105][105];
void dfs()
{
	for(int i=n-1;i>=1;i--)
	{
		for(int j=1;j<=i;j++)
		{
			for(int l=0;l<=n-i+1 && l<=K;l++)
			{
				dp[i][j][l]=max(dp[i+1][j][l]+a[i][j],dp[i+1][j+1][l]+a[i][j]);
				if(l==0)break;
				dp[i][j][l]=max(dp[i][j][l],dp[i+1][j][l-1]+3*a[i][j]);
				dp[i][j][l]=max(dp[i][j][l],dp[i+1][j+1][l-1]+3*a[i][j]);
			}
			
		}
	}
}
int main()
{
	memset(dp,-0x3f,sizeof(dp));
	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]=3*a[n][i];
	}
	dfs();
	ll ans=-0x3f;
	for(int i=0;i<=min(n,K);i++)
	{
	
		ans=max(ans,dp[1][1][i]);
	}
	cout<<ans;
	return 0;
}