#include <stdio.h>
#include <string.h>
#define NMAX 1005
int n,k,A[NMAX][NMAX];
int val,rez,S1[NMAX][NMAX],S2[NMAX][NMAX],S3[NMAX][NMAX],S4[NMAX][NMAX],S5[NMAX][NMAX],best[NMAX][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++)
			S1[i][j]=S1[i-1][j]+A[i][j];
	for (i=1; i<=n; i++)
		for (j=1; j<=i; j++)
			S2[i][j]=S2[i-1][j-1]+A[i][j];
	for (i=1; i<=n; i++)
		for (j=i; j>=1; j--)
			S3[i][j]=S3[i][j+1]+A[i][j];
	for (i=n; i>=1; i--)
		for (j=1; j<=i; j++)
			S4[i][j]=S4[i+1][j]+S3[i][j];
	for (i=n; i>=1; i--)
		for (j=i; j>=1; j--)
			S5[i][j]=S5[i][j+1]+S2[n][j+n-i]-S2[i-1][j-1];
	
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
		{
			best[i+1][j+1]=max(best[i+1][j+1],best[i][j]+S1[n][j]-S1[i-1][j]);
			best[i+1][j]=max(best[i+1][j],best[i][j]+S2[n][j+n-i]-S2[i-1][j-1]);
		}
	
	for (i=1; i<=n; i++)
		for (j=1; j<=i; j++)
		{
			nrop=j-1+i-j;
			if (nrop>k)
				continue ;
			nrop=k-nrop;
			val=best[i][j]+S4[n-nrop+1][j]-(S5[n-nrop+1][j+(n-nrop+1)-i+1]);
			rez=max(rez,val);
		}
	printf("%d\n",rez);
	return 0;
}