#include<iostream>
#include<cstdio>
using namespace std;
int n,k;
int mp[110][110];
long long dp[110][110][5010];
long long ans=-4e18;
int main()
{
	cin>>n>>k;
	if(k>n) k=n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			cin>>mp[i][j];
	for(int i=1;i<=n;i++)
		for(int j=0;j<=n;j++)
			for(int t=0;t<=k;t++)
				dp[i][j][t] = -4e18;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			for(int t=0;t<=k;t++)
			{
				dp[i][j][t] = max(max(dp[i-1][j][t],dp[i-1][j-1][t])+mp[i][j],dp[i][j][t]);
//				printf("1. %d %d %d is %d %d %d + %d = %d\n",i,j,t,i-1,dp[i-1][j][t]>dp[i-1][j-1][t]?j:j-1,t,mp[i][j],dp[i][j][t]);
				if(t>0) dp[i][j][t] = max(max(dp[i-1][j][t-1],dp[i-1][j-1][t-1])+mp[i][j]*3,dp[i][j][t]);
//				if(t<k) printf("2. %d %d %d is %d %d %d + %d = %d\n",i,j,t+1,i-1,dp[i-1][j][t]>dp[i-1][j-1][t]?j:j-1,t,mp[i][j]*3,dp[i][j][t+1]);
			}
	for(int i=1;i<=n;i++)
		for(int j=0;j<=k;j++)
			ans = max(ans,dp[n][i][j]);
	cout<<ans;
	return 0;
}