#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=1e18;
inline int read()
{
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*w;
}
int n,a[101][101],k,f[5051][101][2],ans=-INF;
main()
{
	n=read();k=read();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)a[i][j]=read();
	}
	f[0][1][1]=a[1][1];f[1][1][1]=a[1][1]*3;
	if(n==1)
	{
		ans=max(ans,f[0][1][1]);
		ans=max(ans,f[1][1][1]);
		cout<<ans;
		return 0; 
	}
	if(k>n)k=n;
	for(int i=2;i<=n;i++)
	{
		int u=i%2;
		for(int j=1;j<=i;j++)
		{
			for(int z=1;z<=k;z++)
			{
				f[z][j][u]=-INF;
				if(j==1)
				{
					f[z][j][u]=max(f[z][j][u^1]+a[i][j],f[z-1][j][u^1]+a[i][j]*3);
					if(i==n)
					{
						ans=max(ans,f[z][j][u]);
					}
					continue;
				}
				if(j==i)
				{
					f[z][j][u]=max(f[z][j-1][u^1]+a[i][j],f[z-1][j-1][u^1]+a[i][j]*3);
					if(i==n)
					{
						ans=max(ans,f[z][j][u]);
					}
					continue;
				}
				if(j-1>=1)f[z][j][u]=max(f[z][j][u],f[z-1][j-1][u^1]+a[i][j]*3);
				if(j<i)f[z][j][u]=max(f[z][j][u],f[z-1][j][u^1]+a[i][j]*3);
				if(j-1>=1)f[z][j][u]=max(f[z][j][u],f[z][j-1][u^1]+a[i][j]);
				if(j<i)f[z][j][u]=max(f[z][j][u],f[z][j][u^1]+a[i][j]);
				if(i==n)
				{
					ans=max(ans,f[z][j][u]);
				}
			}
		}
	}
	cout<<ans;
	return 0;
}