#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,ip,sip,scrt,j,ramase,stotal;
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];
		for ( j = 1 ; j <= n - ip ; ++j ){
			scrt += S1[ip+j][j];
			if ( j-(n-ip-ramase) >= 0 && j > ramase ){
				scrt = scrt - S2[j+ip][j-(n-ip-ramase)] + S2[ip][j-(n-ip-ramase)] - S1[ip+j][j-(n-ip-ramase+1)];
				if ( scrt < local_min )	local_min = scrt;
			}
			if ( n - ip - j <= ramase && j >= ramase ){
				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;
}