#include <cstdio>
#include <cstring>

#define NMAX 1005

int N, K, i, j, x, A[NMAX][NMAX], Col[NMAX][NMAX], Lin[NMAX][NMAX], Diag[NMAX][NMAX], D[NMAX][NMAX], Min, STotal;

inline int MIN( int x, int y )
{
	return ( x < y ) ? x : y;
}

int main()
{
	freopen("ferma2.in", "r", stdin);
	freopen("ferma2.out", "w", stdout);
	
	STotal = 0;
	scanf("%d%d", &N, &K);
	for( i = 1; i <= N; ++i )
		for( j = 1; j <= i; ++j )
		{
			scanf("%d", &x);
			A[j][N-i+1] = x;
			STotal += x;
		}
	if( !K )
	{
		printf("0\n");
		return 0;
	}
	else if( K == N )
	{
		printf("%d\n", STotal);
		return 0;
	}
	
	memset( Lin, 0, sizeof(Lin) );
	memset( Col, 0, sizeof(Col) );
	memset( Diag, 0, sizeof(Diag) );
	memset( D, 0, sizeof(D) );
	
	for( i = 1; i <= N; ++i )
		for( j = 1; j <= N - i + 1; ++j )
			Lin[i][j] = Lin[i][j-1] + A[i][j], Col[i][j] = Col[i-1][j] + A[i][j], Diag[i][j] = Diag[i-1][j+1] + A[i][j];
	
	for( i = 1; i <= K + 1; ++i )
			D[1][1] += Lin[i][N-K-i+1];
	Min = D[1][1];
	for( j = 2; j <= K + 1; ++j )
		D[1][j] = D[1][j-1] - Col[N-K][j-1] + Diag[N-K][j], Min = MIN( Min, D[1][j] );
	
	for( i = 2; i <= K + 1; ++i )
		for( j = 1; j <= K + 2 - i; ++j )
			D[i][j] = D[i-1][j] - ( Lin[i-1][j+N-K-1] - Lin[i-1][j-1] ) + ( Diag[i+N-K-1][j] - Diag[i-1][j+N-K] ), Min = MIN( Min, D[i][j] );
	
	printf("%d\n", STotal - Min);
	
	return 0;
}