#include<fstream>
using namespace std;
int N,M,K,A[1010][1010],sum,sol=2000000000;
int sumL[2000][2000],sumC[2000][2000],sumD[2000][2000],best[2000][2000];

void Citire()
{
	int i,j,x,lim;
	ifstream fin("ferma2.in");
	fin>>N>>K;
	if(K==0)
	{
		sol=0;
		return;
	}
	M=N-K;
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=i;j++)
		{
			fin>>A[i][j];
			sumL[i][j]=sumL[i][j-1]+A[i][j];
			sumC[i][j]=sumC[i-1][j]+A[i][j];
			sumD[i][j]=sumD[i-1][j-1]+A[i][j];
			sum+=A[i][j];
		}
	}
	if(K==N)
	{
		sol=sum;
		return;
	}
	lim=N+M;
	for(i=1;i<=N;i++)
	{
		x=sumL[i][i];
		for(j=i+1;j<=lim;j++)
			sumL[i][j]=x;
	}
	fin.close();
}

void Rezolvare()
{
	int i,j,lim,suma=0;
	for(i=1;i<=M;i++)
		for(j=1;j<=i;j++)
			suma+=A[i][j];
	best[M][1]=suma;
	sol=suma;
	for(j=2;j<=M;j++)
	{
		best[M][j]=best[M][j-1]-sumC[M][j-1];
	}
	for(i=M+1;i<=N;i++)
	{
		lim=i-M+1;
		for(j=1;j<=lim;j++)
		{
			best[i][j]=best[i-1][j]-(sumD[i-1][j+M-1]-sumD[i-M-1][j-1])+(sumL[i][j+M-1]-sumL[i][j-1]);
			sol=min(sol,best[i][j]);
		}
		for(j=lim+1;j<=i;j++)
			best[i][j]=best[i-1][j]-(sumD[i-1][j+M-1]-sumD[i-M-1][j-1])+(sumL[i][j+M-1]-sumL[i][j-1]);
	}
	sol=sum-sol;
}

void Afisare()
{
	ofstream fout("ferma2.out");
	fout<<sol<<"\n";
	fout.close();
}

int main()
{
	Citire();
	if(sol==2000000000)
		Rezolvare();
	Afisare();
	return 0;
}