#include <cstdio>
#include <fstream>
#include <algorithm>

using namespace std;

#define N 1001

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

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];
			l[i][j]=l[i][j-1]+a[i][j];
			c[i][j]=c[i-1][j]+a[i][j];
		}
}

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-1][i];
	return s;
}

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

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

int main ()
{
	read ();
	printf("\n");
	solve ();
	freopen ("ferma2.out","w",stdout);
	printf("%d",sol);
	return 0;
}