#include <fstream>
using namespace std;

ifstream fi ("ferma2.in");
ofstream fo ("ferma2.out");

const int dim = 1005;
int Po[dim][dim], Pv[dim][dim], Pd[dim][dim], A[dim][dim], N, K, S, SM, T;

void back (int x1, int y1, int x2, int y2, int k)
{
	if (T < 0)
		return;
	T += 3500;
	
	if (k == K)
	{
		SM = S > SM ? S : SM;
		return;
	}
	
	S += Po[x2][y2] - Po[x2][y1-1];
	back (x1, y1, x2-1, y2-1, k+1);
	S -= Po[x2][y2] - Po[x2][y1-1];
	
	S += Pv[x2][y1] - Pv[x1-1][y1];
	back (x1+1, y1+1, x2, y2, k+1);
	S -= Pv[x2][y1] - Pv[x1-1][y1];
	
	S += Pd[x2][y2] - Pd[x1-1][y1-1];
	back (x1+1, y1, x2, y2-1, k+1);
	S -= Pd[x2][y2] - Pd[x1-1][y1-1];
}

void greedy (int x1, int y1, int x2, int y2, int k)
{
	if (k == K)
	{
		SM = S > SM ? S : SM;
		return;
	}
	
	int a = Po[x2][y2] - Po[x2][y1-1];
	int b = Pv[x2][y1] - Pv[x1-1][y1];
	int c = Pd[x2][y2] - Pd[x1-1][y1-1];	
	if (c > a && c > b)
	{
		S += c;
		greedy (x1, y1, x2-1, y2-1, k+1);
		S -= c;
	}
	else if (b > a && b > c)
	{
		S += b;
		back (x1+1, y1+1, x2, y2, k+1);
		S -= b;
	}
	else if (a > b && a > c)
	{
		S += a;
		back (x1+1, y1, x2, y2-1, k+1);
		S -= a;
	}
	else
	{
		fo << "error";
	}
}

void cit ()
{
	int i, j;
	fi >> N >> K;
	for (i = 1; i <= N; i++)
		for (j = 1; j <= i; j++)
		{
			fi >> A[i][j];
			
			Po[i][j] = A[i][j] + Po[ i ][j-1];
			Pv[i][j] = A[i][j] + Pv[i-1][ j ];
			Pd[i][j] = A[i][j] + Pd[i-1][j-1];
		}
}

int main ()
{
	cit ();
	
	//back (1, 1, N, N, 0);
	greedy (1, 1, N, N, 0);
	
	fo << SM;
	
	return 0;
}