#include <cstdio>
#include <fstream>

using namespace std;

#define N 1001

int a[N][N],d[N][N],c[N][N],l[N][N],n,k,sol;

void read ()
{
	ifstream in ("ferma2.in");
	in>>n>>k;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=i;++j)
		{
			in>>a[i][j];
			d[i][j]=d[i-1][j-1]+a[i][j];
			c[i][j]=a[i][j]+c[i-1][j];
			l[i][j]=a[i][j]+l[i][j-1];
		}
}

int dig (int m)
{
	int s=0;
	for(int i=n;m;--i,--m)
		s+=d[n][i];
	return s;
}

int col (int q,int m)
{
	int s=0;
	for(int i=1;m;++i,--m)
		s+=(c[n][i]-c[q][i]);
	return s;
}

int lin (int q,int w,int m)
{
	int s=0;
	for(int i=n;m;--m)
		s+=(l[i][i]-(l[i][i]-l[i][i-q])-l[i][w]);
	return s;
}

void solve ()
{
	for(int i=0;i<=k;++i)
		for(int j=0;j<=k;++j)
		{
			int s=0,q=k-(i+j);
			if(q>=0)
			{
				if(i)
					s+=dig(i);
				if(j)
					s+=col(i,j);
				if(q)
					s+=lin(i,j,q);
				sol=max(sol,s);
			}
		}
}

void out ()
{
	freopen ("ferma2.out","w",stdout);
	printf("%d",sol);
}

int main ()
{
	read ();
	solve ();
	out ();
	return 0;
}