#include <cstdio>
#include <string>
#include <cstring>
#define MAXN 1005

using namespace std;


int A[MAXN][MAXN];
int N, K, s;
int sD[MAXN][MAXN], sJ[MAXN][MAXN], D[2][MAXN];
int main() {

	freopen("ferma2.in", "r", stdin);
	freopen("ferma2.out", "w", stdout);

	scanf("%d %d\n", &N, &K);

	for(int i = 1; i <= N; i++)
		for(int j = 1; j <= i; j++) {
			scanf("%d", &A[i][j]);
			s += A[i][j];
		}
	
//	printf("%d\n", s);
	//Suma pe diagonala
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= i; j++) {
			sD[i][j] = sD[i - 1][j - 1] + A[i][j];
	//		printf("%d ", sD[i][j]);
		}
	//	printf("\n");
	}
	//Suma de sus in jos
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= i; j++) {
			sJ[i][j] = sJ[i - 1][j] + A[i][j];
	//		printf("%d ", sJ[i][j]);
		}
	//	printf("\n");
	}
	//Dinamica pe triunghi de N-K / N-K;
	int l = N - K, St = 0, minSt;
	if(1 > l) St = s;
	for(int i = 1; i <= l; i++) {
		for(int j = 1; j <= i; j++)
			St += A[i][j];
	}
	if(l == N) St = 0;
	D[0][l] = St;
	int cur = 1, ant = 0;
	
	minSt = St;

	for(int i = l + 1; i <= N; i++) {
		int Sdr = 0;
		if (i > N) break;	
		for(int j = 1; j <= l; j++)
			Sdr += A[i][j];
		D[cur][l] = D[ant][l] - (sD[i - 1][l] - sD[i - l - 1][0]) + Sdr; 
		minSt = min(D[cur][l], minSt);	
//		printf("%d ", D[cur][l]);
		if(l + 1 > i) continue;
		for(int j = l + 1; j <= i; j++) {
			D[cur][j] = D[cur][j - 1];
			D[cur][j] = D[cur][j] + (sD[i][j] - sD[i - l][j - l]) - (sJ[i][j - l] - sJ[i - l][j - l]);
			if(minSt > D[cur][j])
				minSt = D[cur][j];
//			printf("%d ", D[cur][j] );
		}
//		printf("\n");
		ant = cur; cur ^= 1;
	}
	printf("%d\n", s - minSt);	
	return 0;
}