#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
const int MX=10,inf=0x7ffffff;
int mp[MX][MX],f[MX][MX][MX];

int dfs(int x,int y,int k){
	//printf("%d***%d***%d\n",x,y,k);
	if(x==n) return mp[x][y];
	if(f[x][y][k]) return f[x][y][k];
	int a=dfs(x+1,y,k-1),b=dfs(x+1,y+1,k-1);
	if(k>0){
		f[x][y][k]=max(f[x][y][k],a+3*mp[x][y]);
		f[x][y][k]=max(f[x][y][k],b+3*mp[x][y]);
	}
	f[x][y][k]=max(f[x][y][k],a+mp[x][y]);
	f[x][y][k]=max(f[x][y][k],b+mp[x][y]);
	return f[x][y][k];
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++) scanf("%lld",&mp[i][j]);
	}
	printf("%lld",dfs(1,1,k));
	return 0;
}