#include <fstream>
using namespace std;
const int N = 1005;
struct tip{int AL, AC, BL, BC, CL, CC, rez;};
tip d[N][3];
int a[N][N];
int SL[N][N], SC[N][N], SD[N][N];
int n, K;

int main(){
	ifstream fin("ferma2.in");
	ofstream fout("ferma2.out");
	int i, j, x, k;
	fin >> n >> K;
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= i; ++j)
			fin >> a[i][j];
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= i; ++j)
			SL[i][j] = (int) SL[i][j - 1] + a[i][j];
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= i; ++j)
			SC[i][j] = (int) SC[i - 1][j] + a[i][j];
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= i; ++j)
			SD[i][j] = (int) SD[i - 1][j - 1] + a[i][j];
	tip X;
	X.AL = 1;	X.AC = 1;
	X.BL = n;	X.BC= 1;
	X.CL = n;   X.CC = n;
	X.rez = 0;
	int L, C, D;
	d[0][1] = d[0][0] = d[0][2] = X;
	
	for(i = 1; i <= K; ++i)
		for(j = 0; j <= 2; ++j)
			for(k = 0; k <= 2; ++k){
				X = d[i - 1][k];
				L = X.rez + SL[X.BL][X.CC] - SL[X.BL][X.BC - 1];
				C = X.rez + SC[X.BL][X.BC] - SC[X.AL - 1][X.AC];
				D = X.rez + SD[X.CL][X.CC] - SD[X.AL - 1][X.AC - 1];
				
				if(j == 0 && L > d[i][j].rez){
					X.rez = L;	
					--X.BL;
					--X.CC;
					--X.CL;
					d[i][j] = X;
				}
				
				if(j == 1 && C > d[i][j].rez){
					X.rez = C;
					++X.AL;
					++X.AC;
					++X.BC;
					d[i][j] = X;
				}

				if(j == 2 && D > d[i][j].rez){
					X.rez = D;
					++X.AL;
					--X.CC;
					d[i][j] = X;
				}
			}
//	for(i = 1; i <= n; ++i){
//		for(j = 1; j <= i; ++j)
//			fout << SD[i][j] << " ";
//		fout << '\n';
//	}

	int max = 0;
	for(j = 0; j <= 2; ++j)
		if(max < d[K][j].rez)
			max = d[K][j].rez;	
		max = X.rez;
	fout << max << '\n';
	return 0;
}