#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define for1(i,a,b) for(ll i=(ll)a;i<=(ll)b;++i)
#define for0(i,a,b) for(ll i=(ll)a;i>=(ll)b;--i)
ll dp[110][110][110], n, k, a[110][110], nx[2] = {-1, -1}, ny[2] = {0, -1};
ll dfs (ll x, ll y, ll s){
	if (x<1 or y<1 or x>n or y>x)	return -1e17;
	if (x == n){
		if (s>0 and a[x][y]>0){
			return a[x][y]*3;
		}
		return a[x][y];
	}
	if (dp[x][y][s] != -1e17)				return dp[x][y][s];
	if (s > 0){
		for1 (i, 0, 1){
			dp[x][y][s] = max (dp[x][y][s], dfs (x-nx[i], y-ny[i], s)+a[x][y]);
			if (a[x][y] > 0 and s > 0)	dp[x][y][s] = max (dp[x][y][s], dfs (x-nx[i], y-ny[i], s-1)+a[x][y]*3LL);
		}
		return dp[x][y][s];
	}
	return dp[x][y][s] = max (dfs (x+1, y, s)+a[x][y], dfs (x+1, y+1, s)+a[x][y]);
}
int main(){
	cin >>n >>k;
	for1 (i, 0, n+1){
		for1 (j, 0, n+1){
			for1 (l, 0, n+1){
				dp[i][j][l] = -1e17;
			}
		}
	}
	for1 (i, 1, n){
		for1 (j, 1, i){
			cin >>a[i][j];
		}
	}
	cout <<dfs (1, 1, k);
	return 0;
}