#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int N , a[1005][1005] , K , sol = 0 , linie = 0 , col = 0 , diag = 0;

void up_linie (int D)
{
	linie = 0;
	
	for (int i = D ; i <= N ; ++i)
		linie += a[i][D];
}
void up_col (int D)
{
	col = 0;
	
	for (int i = 1 ; i <= N - D + 1 ; ++i)
		col += a[N - D + 1][i];
}
void up_diag (int D)
{
	diag = 0;
	
	for (int i = D ; i <= N ; ++i)
		diag += a[i][i - D + 1];
}

int main ()
{
	freopen ("ferma2.in" , "r" , stdin);
	freopen ("ferma2.out" , "w" , stdout);
	
	scanf ("%d %d" , &N , &K);
	
	for (int i = 1 ; i <= N ; ++i)
		for (int j = 1 ; j <= i ; ++j)
			scanf ("%d" , &a[i][j]);
	
	for (int i = 1 ; i <= N ; ++i)
	{
		linie += a[i][1];
		diag += a[i][i];
		col += a[N][i];
	}
	
	int dim = N , aux;
	
	for (int t = 1 ; t <= K ; ++t)
	{
		aux = max (max (linie , col) , diag);
		
		sol += aux;
		
		if (aux == linie)
		{
			up_linie(t + 1);
			diag -= a[t][t];
			col -= a[dim][t];
		}
		
		else if (aux == col)
		{
			up_col(t + 1);
			linie -= a[dim][1];
			diag -= a[dim][dim];
			--dim;
		}
		
		else
		{
			up_diag (t + 1);
			linie -= a[t][1];
			col -= a[dim][dim - t + 1];
		}
	}
	
	printf ("%d" , sol);
	
	return 0;
}