#include <iostream>
#include <cstdio>
#define inf -1e18
using namespace std;
typedef long long ll;
const int N=110;
int n,k;
ll dp[N][N][N];
bool f[N][N][N];
int a[N][N];
ll dfs(int x,int y,int m)
{
  if(f[x][y][m]) return dp[x][y][m];
  f[x][y][m]=1;
  if(x==n&&m>=1)  return dp[x][y][m]=1ll*3*a[x][y];
  if(x==n&&m<1)  return dp[x][y][m]=1ll*a[x][y];
  dp[x][y][m]=inf;
  dp[x][y][m]=max(dfs(x+1,y,m)+a[x][y],dfs(x+1,y+1,m)+a[x][y]);
  if(m>=1)
    dp[x][y][m]=max(dp[x][y][m],max(dfs(x+1,y,m-1)+1ll*3*a[x][y],dfs(x+1,y+1,m-1)+1ll*3*a[x][y]));
  return dp[x][y][m];
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=i;j++)
	    scanf("%d",&a[i][j]);
	if(k>n)  k=n;
	printf("%lld\n",dfs(1,1,k));
	return 0;
}