#include <stdio.h>
#define NMAX 1005
int n,k,A[NMAX][NMAX];
int val,rez,B[NMAX][NMAX],S1[NMAX][NMAX],S2[NMAX][NMAX],S3[NMAX];
inline int max(int x,int y)
{
	return x>y ? x : y;
}
int main()
{
	freopen("ferma2.in","r",stdin);
	freopen("ferma2.out","w",stdout);
	scanf("%d%d",&n,&k);
	int i,j,val,nrop;
	for (i=1; i<=n; i++)
		for (j=1; j<=i; j++)
			scanf("%d",&A[i][j]);
		
	for (i=1; i<=n; i++)
		for (j=1; j<=i; j++)
			B[i][j]=B[i-1][j]+A[i][j];
	for (i=1; i<=n; i++)
		for (j=1; j<=i; j++)
			S1[i][j]=S1[i][j-1]+B[i][j];
	
	for (i=1; i<=n; i++)
		for (j=1; j<=i; j++)
			B[i][j]=B[i-1][j-1]+A[i][j];
	for (i=1; i<=n; i++)
		for (j=i; j>=1; j--)
			S2[i][j]=S2[i][j+1]+B[i][j];
		
	for (i=n; i>=1; i--)
		for (j=1; j<=i; j++)
			B[i][j]=B[i][j-1]+A[i][j];
	for (i=n; i>=1; i--)
		S3[i]=S3[i+1]+B[i][i];
		
	for (i=1; i<=n; i++)
		for (j=1; j<=i; j++)
		{
			nrop=j-1+i-j;
			if (nrop>k)
				continue ;
			val=S1[n][j-1]+S2[n][j+n-i+1];
			if (i-2>0)
				val-=S1[i-2][j-1];
			nrop=k-nrop;
			if (nrop)
				val+=S3[n-nrop+1]-(S1[n][j-1]-S1[n-nrop][j-1])-(S2[n][j+n-i+1]-S2[n-nrop][j+(n-nrop)-i+1]);
			rez=max(rez,val);
		}
	printf("%d\n",rez);
	return 0;
}