#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("ferma2.in");
ofstream fout ("ferma2.out");

int map[1000][1000] , n , k ;
int suma_coloana , suma_diagonala , suma_linie , profit , suma_secundara , suma ;

void sum ()
{
    suma_coloana = 0 ;
    suma_diagonala = 0 ;
    suma_linie = 0 ;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        suma_diagonala = suma_diagonala + map[i][i];
        suma_coloana = suma_coloana + map[i][1];
        suma_linie = suma_linie + map[n][i];
    }
}

int main()
{
    int i , j ;
    fin >> n >> k ;
    for ( i = 1 ; i <= n ; i ++ )
    {
        for ( j = 1 ; j <= i ; j ++ )
        {
            fin >> map [i] [j] ;
        }
    }

    while ( k > 0 )
    {
        sum();
        suma_secundara = max ( suma_linie , suma_coloana );
        suma = max ( suma_diagonala , suma_secundara );


        if ( suma == suma_linie ) n--;

        if ( suma == suma_coloana )
        {
            for ( i = 1 ; i <= n ; i ++)
                for ( j = 1 ; j <= i ; j ++ ) map[i][j]=map[i+1][j+1];
            n--;
        }

        if ( suma == suma_diagonala )
        {
            for ( i = 1 ; i <= n ; i ++ )
                for ( j = 1 ; j <= n ; j ++ ) map[i][j] = map[i+1][j];
            n--;
        }
        k--;
        profit = profit + suma ;
    }
    fout << profit ;
}