#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],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=1; j<=i; j++)
			S3[i][j]=S3[i][j-1]+A[i][j];
	
	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]);
		}
	
	int t,st;
	for (i=1; i<=n; i++)
		for (j=1; j<=i; j++)
		{
			nrop=j-1+i-j;
			if (nrop>k)
				continue ;
			nrop=k-nrop;
			st=j+n-i;
			val=best[i][j];
			for (t=1; t<=nrop; t++)
				val+=S3[n-t+1][st]-S3[n-t+1][j-1],st--;
			rez=max(rez,val);
		}
	printf("%d\n",rez);
	return 0;
}