# include <fstream>
# include <iostream>
# define DIM 1003
# define max(a,b) (a>b?a:b)
using namespace std;
int n, K, a[DIM][DIM], sol, v[DIM][DIM], o[DIM][DIM], d[DIM][DIM], ds[DIM][DIM];

void read ()
{
	ifstream fin ("ferma2.in");
	fin>>n>>K;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=i;++j)
		{
			fin>>a[i][j];
			v[i][j]=v[i-1][j]+a[i][j];
			d[i][j]=d[i-1][j-1]+a[i][j];
		}
}

void solve ()
{
	for(int i=1;i<=n;++i)
		for(int j=1;j<=i;++j)
			v[i][j]+=v[i][j-1];
	for(int i=n;i;--i)
	{
		int s=0;
		for(int j=i;j;--j)
			s+=a[i][j],
			o[i][j]=o[i+1][j]+s;
	}
	for(int i=1;i<=n;++i)
		for(int j=i;j;--j)
			ds[i][j]=ds[i-1][j]+d[i][j];
	for(int i=1;i<=n;++i)
		for(int j=i;j;--j)
			d[i][j]+=d[i][j+1];
	for (int i=0;i<=K;++i)
		for(int j=0;i+j<=K;++j)
		{
			int k=K-i-j;
			sol=max(sol,v[n][i]+o[n-j+1][i+1]+d[n-j][n-j-k+1]-ds[i+k-1][i]);
		}
}

int main ()
{
	read ();
	solve ();
	ofstream fout ("ferma2.out");
	fout<<sol;
	return 0;
}