#include <cstdio>
#include <cstring>

#define NMAX 1005
#define ll long long

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

inline ll MIN( ll X, ll Y )
{
	return ( X < Y ) ? X : Y;
}

int main()
{
	freopen("ferma2.in", "r", stdin);
	freopen("ferma2.out", "w", stdout);
	
	STotal = 0;
	scanf("%lld%lld", &N, &K);
	for( i = 1; i <= N; ++i )
		for( j = 1; j <= i; ++j )
		{
			scanf("%lld", &x);
			A[j][N-i+1] = x;
			STotal += x;
		}
	if( !K )
	{
		printf("0\n");
		return 0;
	}
	else if( K == N )
	{
		printf("%lld\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("%lld\n", STotal - Min);
	
	return 0;
}