#include<iostream>
#include<map>
#define int long long
using namespace std ;
int n = 0 , m = 0 ;
int brike[55][55] = {} ;
bool vis[55][55] = {} ;
//int done[55][55][505][2] = {} ;
struct state
{
	int i , j , cnt ;
	string last ;
	bool operator<(const state& b) const
	{
		if(i != b.i)
			return i < b.i ;
		if(j != b.j)
			return j < b.j ;
		if(cnt != b.cnt)
			return cnt < b.cnt ;
		return last < b.last ;
	}
};
map<state , int> done ;
int dfs(state now)
{
	if(now.cnt == m || now.i == n + 1)
	{
		return 0 ;
	}
	if(done[now])
		return done[now] ;
	int sum = 0 ;
	if(now.j < n - now.i + 1)
	{
		sum = max(sum , dfs((state){now.i , now.j + 1 , now.cnt , now.last})) ;
		if(now.i == 1 || (vis[now.i - 1][now.j] && vis[now.i - 1][now.j + 1]))
		{
			vis[now.i][now.j] = true ;
			sum = max(sum , dfs((state){now.i , now.j + 1 , now.cnt + 1 , now.last}) + brike[now.i][now.j]) ;
			vis[now.i][now.j] = false ;
		}
	}
	else
	{
		string st ;
		for(int i = 1 ; i <= n - now.i + 1 ; ++i)
			st[i - 1] = vis[now.i][i] ? '1' : '0' ;
		sum = max(sum , dfs((state){now.i + 1 , 1 , now.cnt , st})) ;
		if(now.i == 1 || (vis[now.i - 1][now.j] && vis[now.i - 1][now.j + 1]))
		{
			st[n - now.i] = '1' ;
			vis[now.i][now.j] = true ;
			sum = max(sum , dfs((state){now.i + 1 , 1 , now.cnt + 1 , st}) + brike[now.i][now.j]) ;
			st[n - now.i + 1] = '0' ;
			vis[now.i][now.j] = false ;
		}
	}
	return done[now] = sum ;
}
signed main()
{
//	freopen("brike.in" , "r" , stdin) ;
//	freopen("brike.out" , "w" , stdout) ;
	scanf("%lld%lld" , &n , &m) ;
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 1 ; j <= n - i + 1 ; ++j)
		{
			scanf("%lld" , &brike[i][j]) ;
		}
	}
	printf("%lld\n" , dfs((state){1 , 1 , 0 , ""})) ;
	fclose(stdin) ;
	fclose(stdout) ;
	return 0 ;
}