#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;
	for(int i = 1; i <= l; i++)
		for(int j = 1; j <= i; j++)
			St += A[i][j];
	D[0][l] = St;
	int cur = 1, ant = 0;
	
	minSt = St;
//	printf("%d\n", St);
	if(l == 1) {
		int mn = A[1][1];
		for(int i = 1; i <= N; i++)
			for(int j = 1; j <= i; j++)
				mn = max(A[i][j], mn);
		printf("%d\n", mn);
		return 0;
	}
	if(K == 0) {
		printf("%d\n", s);
		return 0;
	}
	for(int i = l + 1; i <= N; i++) {
		int Sdr = 0;
		
		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;  
//		printf("%d ", D[cur][l]);
		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;
}