#include <fstream>
using namespace std;

#define NMAX 1024
ifstream fin("ferma2.in");
ofstream fout("ferma2.out");

int N,K,i,j,k,ii,jj,kk,S,Smax;
int Sl[NMAX][NMAX],Sc[NMAX][NMAX],Sd[NMAX][NMAX];
int S2l[NMAX],S2c[NMAX][NMAX],S2d[NMAX][NMAX];
int A[NMAX][NMAX];

int main() {
	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]=Sl[i][j-1]+A[i][j];
			Sc[i][j]=Sc[i-1][j]+A[i][j];
			Sd[i][j]=Sd[i-1][j-1]+A[i][j];
		}
	
	for(i=1;i<=K;i++) {
		S2l[i]=S2l[i-1]+Sl[N-i+1][N-i+1];
		for(j=1;j<=N;j++) {
			S2c[j][i]=S2c[j][i-1]+Sc[j][i];
			if(j>i)
				S2d[j][i]=S2d[j][i-1]+Sd[j][j-i+1];
		}
	}
	
	if(K==N) {
		Smax=0;
		for(j=1;j<=N;j++)
			Smax+=Sc[N][j];
	}
	else
	for(i=0;i<=K;i++)             // i = linia
		for(j=0;j<=K-i;j++) {     // j = coloana
			k=K-i-j;  			  // k = diagonala
			
			S=S2l[i]+S2c[N-i][j]+S2d[N-i][k];
			
			if(j<=k)
				for(jj=1;jj<=j;jj++)
					S-=Sc[k+jj-1][jj];
			else
				for(kk=1;kk<=k;kk++)
					S-=Sd[kk+j-1][j];
			Smax=max(Smax,S);
		}
	fout << Smax;
}