#include <stdio.h>
using namespace std;

long N, M, Ns, Ms, K;
long F[1001][1001];

long maxlr() {
	long S1, S2, S3;
	long i, j;
	S1 = S2 = S3 = 0;
	for(i = Ns + 1; i <= N; i++)
		S1 += F[i][Ms + 1];
	for(i = Ms + 1; i <= M; i++)
		S2 += F[Ns + 1][i];
	for(i = Ns + 1, j = Ms + 1; i <= N || j <= M; i++, j++)
		S3 += F[i][j];
	if(S1 > S2) {
		if(S1 > S3) {
			Ms++;
			Ns++;
			return S1;
		}
		else {
			Ns++;
			M--;
			return S3;
		}
	}
	else {
		if(S2 > S3) {
			M--;
			N--;
			return S2;
		}
		else {
			Ns++;
			M--;
			return S3;
		}
	}
}

int main() {
	long i, j, S = 0, S1, S2, S3;
	freopen("ferma2.in", "r", stdin);
	freopen("ferma2.out", "w", stdout);
	scanf("%ld %ld", &N, &K);
	M = N;
	for(i = 1; i <= N; i++)
		for(j = 1; j <= i; j++)
			scanf("%ld", &F[i][j]);
	for(i = 1; i <= K; i++) {
		S += maxlr();
	}
	printf("%ld", S);
	return 0;
}