# include <fstream>
using namespace std;
ifstream f ("ferma2.in");
ofstream g ("ferma2.out");
int s=0,s1,s2,s3,a[1006][1006],i,j,n,k,maxim,q,w;

 void asd (int i,int i1,int j1,int i2,int j2)
 {
	 s1=s2=s3=0;
	 for (q=i1;q<=i2;q++)
		 s1+=a[q][j1];
	 for (q=j1;q<=j2;q++)
		 s2+=a[i2][q];
	 w=0;
	 for (q=i1;q<=i2;q++,w++)
		 s3+=a[q][j1+w];
	 
	 maxim=s1;
		 if (s2>maxim)
			 maxim=s2;
		 if (s3>maxim)
			 maxim=s3;
		
		 if (maxim==s1)
		 {
			 s+=s1;
			 if (i<k)
			 asd (i+1,i1+1,j1+1,i2,j2);
		 }
		 else
			 if (maxim==s2)
			 {
				 s+=s2;
				 if (i<k)
				 asd (i+1,i1,j1,i2-1,j2-1);
			 }
			 else
			 {
				 s+=s3;
				 if (i<k)
				 asd (i+1,i1+1,j1,i2,j2-1);
			 }
 }

int main ()
{
	f>>n>>k;
	for (i=1;i<=n;i++)
		for (j=1;j<=i;j++)
			f>>a[i][j];
		
	asd (1,1,1,n,n);
	g<<s;
	return 0;
}