//eudanip
#include<stdio.h>

#define NMAX 1005
#define maxim(a,b) (a>b ? a : b)
#define minim(a,b) (a<b ? a : b)

int line[NMAX],colum[NMAX],sd[NMAX],n;
int d3[NMAX][NMAX],d2[NMAX][NMAX],sum;
int k,d[NMAX][NMAX],sol,a[NMAX][NMAX];
int l[NMAX][NMAX],c[NMAX][NMAX];

int main ()
{
	int i,j,t;

	freopen("ferma2.in","r",stdin);
	freopen("ferma2.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++)
		for(j=1;j<=i;j++)
		{
			scanf("%d",&a[i][j]);
			line[n-i+1]+=a[i][j];
			colum[j]+=a[i][j];
			sd[i-j+1]+=a[i][j];
		}
	for(i=1;i<=n;i++)
	{
		line[i]+=line[i-1];
		colum[i]+=colum[i-1];
		sd[i]+=sd[i-1];
		//printf("line[%d]=%d colum[%d]=%d sd[%d]=%d\n",i,line[i],i,colum[i],i,sd[i]);
	}
	for(i=1;i<=n;i++)
		for(j=1;i+j<=n+1;j++)
		{
			d[i][j]=a[n-i+1][j]+d[i-1][j]+d[i][j-1]-d[i-1][j-1];
			//printf("d[%d][%d]=%d\n",i,j,d[i][j]);
		}
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
		{
			c[i][j]=c[i][j-1]+a[j][i];
			//printf("c[%d][%d]=%d\n",i,j,c[i][j]);
		}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			d2[i][j]=d2[i-1][j]+c[i][minim(i+j-1,n)];

	for(i=1;i<=n;i++)
		for(j=i;j>=1;j--)
			l[i][j]=l[i][j+1]+a[i][j];
		
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			d3[i][j]=d3[i-1][j]+l[n-i+1][maxim(1,i-j+1)];

			
	/*for(i=1;i<=n;i++)
		for(j=1;j<=i;j++)
			printf("d2[%d][%d]=%d\n",i,j,d2[i][j]);*/
	for(i=0;i<=k;i++)
		for(j=0;j<=k-i;j++)
		{
			t=k-i-j;
			sum=line[i]+colum[j]-d[i][j]+sd[t]-d2[j][t]-d3[i][t];
			if(sum==839)
				printf("%d %d %d !!! %d %d %d %d %d %d\n",i,j,t,line[i],colum[j],sd[t],d[i][j],d2[j][t],d3[i][t]);
			sol=maxim(sol,sum);
		}
	printf("%d\n",sol);
	return 0;
}