#include<fstream>
#include<algorithm>
#define dim 1001
using namespace std;
ifstream f("ferma2.in");
ofstream g("ferma2.out");
int n,m,i,j,smax=0,k,x,y,l,i1;
int a[dim][dim];
int min1=1000000;
int max1(int a,int b)
{
	return (a<b)?b:a;  
}
int diag[dim][dim];
int main()
{
	f>>n>>k;
	for(i=1;i<=n;++i)
	{
		for(j=1;j<=i;++j)
		{
			f>>a[i][j];
		smax=smax+a[i][j];
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
		{
			diag[i][j]=diag[i-1][j-1]+a[i][j];
		}
	}
	int col2[dim],diag2[dim];
	int lin3[dim];
	int col3[dim];
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
			lin3[n-i+1]+=a[i][j];
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
			col3[j]=col3[j]+a[i][j];
	}
	for(i=1;i<=n;i++)
	{
		for(j=i,k=1;j>=1;j--,k++)
			diag2[n-i+1]+=a[n+1-k][j];
	}
	/*for(i=n;i>=1;i--)
		diag2[i]=diag[n][i];*/
	/*for(i=1;i<=k;i++)
	{
		if(col3[i]>max1(lin3[i], diag2[i]))
		{
			for(j=1;j<=n;j++)
				a[j][i]=0;
		}
		else
			if(lin3[i]>max1(col3[i], diag2[i]))
			{
				for(j=1;j<=i;j++)
					a[i][j]=0;
			}
			else
				if(diag2[i]>max1(col3[i], lin3[i]))
				{
					
				}
	}*/
	for(i=1;i<=n;i++)
		g<<diag2[i]<<" ";
	g<<smax;
	/*for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
			g<<diag[i][j]<<" ";
		g<<"\n";
	}*/
	/*for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
			g<<a[i][j]<<" ";
		g<<"\n";
	}*/
	int t,r,rez;
	m=n-k;
	for(i=n;i>=m;i--) 
	{ 
		for(j=i;j>=m;j--) 
		{ 
			rez=0; 
			r=m; 
			for(t=j;t>j-m;t--) 
				rez+=(diag[i][t]-diag[i-r][t-r]),r--; 
			if(min1>rez) 
				min1=rez; 
		} 
	}
	g<<smax-min1;
	return 0;
}