#include <iostream>
#include <fstream>
#define N 1001

using namespace std;
ifstream f("ferma2.in");
ofstream g("ferma2.out");

int main() {
	int A[N][N],x[N]={0},y[N]={0},z[N]={0},n,k,i,j,op[N],max=0,p=0,a,b,c;
	
	f>>n>>k;
	for(i=1;i<=n;i++) {
		for(j=1;j<=i;j++) {
			f>>A[i][j];
		}
	}
	
	for(i=n;i>=n-k+1;i--) {
		for(j=n-i+1;j<=n;j++) {
		 	x[n-i+1]+=A[j][n-i+1];
		}
		for(j=1;j<=i;j++) {
			y[n-i+1]+=A[i][j];
		}
		for(j=1;j<=i;j++) {
			z[n-i+1]+=A[j+n-i][j];
		}
	}

	a=b=c=1;
	for(i=1;i<=k;i++) {
				for(int t=1;t<=3;t++) {
		cout<<x[t]<<" "<<y[t]<<" "<<z[t]<<endl;
	}
		if(x[a] > y[b] && x[a] > z[c]) {
			p+=x[a];
			cout<<"Se vinde x "<<x[a]<<endl;
			x[a]=0;
			for(j=b;j<=k;j++) {
				y[j]-=A[n-j+1][a];
				//cout<<A[n-j+1][a]<<endl;
			}
			for(j=c;j<=k;j++) {
				z[j]-=A[j][a];
			//	cout<<A[j][a]<<endl;
			}
			a++;
		} else {
			if(y[b] > x[a] && y[b] > z[c]) {
			p+=y[b];
			cout<<"Se vinde y "<<y[b]<<endl;
			y[b]=0;
			for(j=a;j<=k;j++) {
				x[j]-=A[n-b+1][j];
			}
			for(j=c;j<=k;j++) {
				z[j]-=A[n-b+1][n-j+1];
			}
			b++;
			} else {
				if(z[c] > x[a] && z[c] > y[b]) {
					p+=z[c];
					cout<<"Se vinde z "<<z[c]<<endl;
					z[c]=0;
					for(j=a;j<=k;j++) {
						x[j]-=A[j+b-1][j];
					}
					for(j=b;j<=k;j++) {
						y[j]-=A[n-j+b][n-j+1];
					}
					c++;
				}
			}
		}
	}
	g<<p;
	return 0;
}