#include<stdio.h>

#define maxn 1005
#define INF (1<<30)

FILE*f=fopen("ferma2.in","r");
FILE*g=fopen("ferma2.out","w");

int n,k,i,local_min,best,lin,ip,sip,scrt,j,ramase,stotal,st;
int A[maxn][maxn],S1[maxn][maxn],S2[maxn][maxn],Sdiag[maxn][maxn];

int main () {
	
	fscanf(f,"%d %d",&n,&k);
	
	for ( i = 1 ; i <= n ; ++i ){
		for ( j = 1 ; j <= i ; ++j ){
			fscanf(f,"%d",&A[i][j]); stotal += A[i][j];
			Sdiag[i][j] = Sdiag[i-1][j-1] + A[i][j];
			S1[i][j] = S1[i][j-1] + A[i][j];
			S2[i][j] = S2[i-1][j] + A[i][j];
		}
	}
	
	for ( ip = 0 ; ip <= k ; ++ip ){
		sip = sip + Sdiag[n][n-ip+1]; ramase = k - ip; scrt = 0; local_min = INF; stotal -= Sdiag[n][n-ip+1]; st = 0; lin = ip+1;
		for ( j = 1 ; n - lin >= ramase ; ++j , ++lin ){
			scrt += S1[ip+j][j];
		}
		if ( scrt < local_min )	local_min = scrt;
		for ( ; j + ip <= n ; ++j , ++lin ){
			++st;
			scrt += S1[j+ip][j] - S1[j+ip][st];
			scrt = scrt - S2[lin-1][st] + S2[ip+st-1][st];
			if ( scrt < local_min )	local_min = scrt;
		}
		if ( sip + stotal - local_min > best )	best = sip + stotal - local_min;
	}
	
	fprintf(g,"%d\n",best);
	
	fclose(f);
	fclose(g);
	
	return 0;
}