#include <stdio.h>
#include <queue>
using namespace std;

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

struct tr {
	long S, N, M, Ns, Ms, gv;
};

void trv(long N, long M, long Ns, long Ms, long &S4, long &S5, long &S6) {
	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; i <= N; i++) {
		S3 += F[i][i + (Ns - Ms)];
	}
	S4 = S1;
	S5 = S2;
	S6 = 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;
	queue<tr> q;
	tr tmp;
	for(i = 1; i <= N; i++)
		for(j = 1; j <= i; j++)
			scanf("%ld", &F[i][j]);
	tmp.S = 0;
	tmp.N = N;
	tmp.M = M;
	tmp.Ns = Ns;
	tmp.Ms = Ms;
	tmp.gv = 0;
	q.push(tmp);
	for(; q.front().gv < K;) {
		trv(q.front().N, q.front().M, q.front().Ns, q.front().Ms, S1, S2, S3);
		tmp.S = q.front().S + S1;
		tmp.N = q.front().N;
		tmp.M = q.front().M - 1;
		tmp.Ns = q.front().Ns;
		tmp.Ms = q.front().Ms;
		tmp.gv = q.front().gv + 1;
		if(tmp.S > S)
			S = tmp.S;
		q.push(tmp);
		
		tmp.S = q.front().S + S2;
		tmp.N = q.front().N - 1;
		tmp.M = q.front().M;
		tmp.Ns = q.front().Ns;
		tmp.Ms = q.front().Ms;
		tmp.gv = q.front().gv + 1;
		if(tmp.S > S)
			S = tmp.S;
		q.push(tmp);
		
		tmp.S = q.front().S + S3;
		tmp.N = q.front().N;
		tmp.M = q.front().M;
		tmp.Ns = q.front().Ns + 1;
		tmp.Ms = q.front().Ms + 1;
		tmp.gv = q.front().gv + 1;
		if(tmp.S > S)
			S = tmp.S;
		q.push(tmp);
		q.pop();
	}
	printf("%ld", S);
	return 0;
}