#include <cstdio>

int n,k,i,j,nr,maxx,suma=0,max1,max2,max3,f;
int a[1010][1010];

inline int max(int a, int b) { return a>b?a:b; }



int main(){
	
	freopen("ferma2.in","r",stdin);
	freopen("ferma2.out","w",stdout);
	
	scanf("%d %d", &n, &k);
	
	for (i=1;i<=n;++i)
		 for (j=1;j<=i;++j)
			  scanf("%d", &a[i][j]);
	nr=f=0;	 
	while(k--){
		nr++;
        max1=max2=max3=0;
        for (i=nr;i<=n;++i){
             max1+=a[i][nr];
             max2+=a[i][i-f];
             max3+=a[nr][i];
        }
        maxx=max(max1,max(max2,max3));
        if (maxx==max1)
             for (i=nr;i<=n;++i)
				  a[i][nr]=0;
		else
		if (maxx==max2){
             for (i=nr;i<=n;++i)
				  a[i][i-f]=0;
              f++;
		}
		else
		if (maxx==max3)
             for (i=nr;i<=n;++i)
				  a[nr][i]=0;
			// printf("%d\n", maxx);
        suma+=maxx;			 
	}
	
	printf("%d\n", suma);
	
	return 0;
	
}