#include <stdio.h>
#define LEN 1005

int M[LEN][LEN];
int n, k;

int 
main(void)
{
    int i, j;
    int coloana, linie;
    int s1, s2, s3, S;
    
    freopen("ferma2.in", "r", stdin);
    freopen("ferma2.out", "w", stdout);
    
    scanf("%d %d", &n, &k);
    
    if(k < n && n <= 1000)
    {
        for(i = 0; i < n; i++)
        	for(j = 0; j <= i; j++)
        	      scanf("%d", &M[i][j]);
        
        S = coloana = linie = 0;
        
        while(k > 0)
        {
                s1 = s2 = s3 = 0;
                for(i = linie; i <= n; i++)
                      s1 += M[i][coloana];
                for(i = coloana; i <= n; i++)
                      s2 += M[n - 1][i];
                for(i = 0; i <= n; i++)
                      s3 += M[linie + i][coloana + i];           
                
                if(s1 >= s2 && s1 >= s3)
                     S += s1, coloana++, linie++, printf("s1");
                else if(s2 >= s1 && s2 >= s3)
                     S += s2, printf("s2");
                else if(s3 >= s1 && s3 >= s2)
                     S += s3, linie++, printf("s3");
                
                n--;
                k--;
        }
        
        printf("%d", S);
    }
    return 0;
}