#include <fstream>
using namespace std;

#define NMAX 1010
#define in "ferma2.in"
#define out "ferma2.out"

struct varf
{
	int l,c;
};

varf v1,v2,v3;

char buff[10000];
int a[NMAX][NMAX],dp[NMAX];

inline int sumL()
{
	int i,ans = 0;
	for(i = v2.c; i <= v3.c; i++)
		ans += a[v2.l][i];
	return ans;
}

inline int sumC()
{
	int i,ans = 0;
	for(i = v1.l; i <= v2.l; i++)
		ans += a[i][v1.c];
	return ans;
}

inline int sumD()
{
	int i,ans = 0,c = v1.c;
	for(i = v1.l; i <= v3.l; i++)
		ans += a[i][c],c++;
	return ans;
}

ifstream fin(in);
ofstream fout(out);

int main()
{
	int N,K,val1,val2,val3,updated = 0,i,j;
	
	fin>>N>>K;
	
	for(i = 1; i <= N; i++)
		for(j = 1; j <= i; j++)
			fin>>a[i][j];
	
	v1.l = 1;
	v1.c = 1;
	v2.l = N;
	v2.c = 1;
	v3.l = N;
	v3.c = N;
		
	dp[0] = 0;
	for(i = 1; i <= K; i++)
	{	
		updated = 0;
		val1 = sumL();
		val2 = sumC();
		val3 = sumD();
		if(val1 >= val2 && val1 >= val3 && !updated)
		{
			dp[i] = dp[i-1] + val1;
			v2.l--;
			v3.l--;
			updated = 1;
		}
		if(val2 >= val1 && val2 >= 3 && !updated)
		{
			dp[i] = dp[i-1] + val2;
			v1.l++;
			v1.c++;
			v2.c++;
			updated = 1;
		}
		if(val3 >= val1 && val3 >= val2 && !updated)
		{
			dp[i] = dp[i-1] + val3;
			v1.l++;
			v3.c--;
			updated = 1;
		}
	}
	fout<<dp[K]<<'\n';
	fin.close();
	fout.close();
	return 0;
}