#include<bits/stdc++.h>
using namespace std;
int n,k,a[105][105];
long long rp[105][105][105];
long long dfs(int x,int y,int k1)
{
	if(x==n+1)return 0;
	if(rp[x][y][k1]!=rp[0][0][0])return rp[x][y][k1];
	for(int i=0;i<=1;i++)
	{
		rp[x][y][k1]=max(rp[x][y][k1],dfs(x+1,y+i,k1)+a[x][y]);
		if(k1>0)
			rp[x][y][k1]=max(rp[x][y][k1],dfs(x+1,y+i,k1-1)+a[x][y]*3);
	}
	return rp[x][y][k1];
}
int main()
{
	memset(rp,-0x7f,sizeof(rp));
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			scanf("%d",&a[i][j]);
	dfs(1,1,min(k,n));
	printf("%lld",rp[1][1][min(k,n)]);
	return 0;
}