我参照数字三角形来做的，从到达最后一层的结果上，对于每一个到大最后一层一定为最优解，存下他们的路径，然后对于大的数使用*3，为什么后面的数据过不了，而且一开始的测试样例也不对，哭了。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <vector>

using namespace std;

const int N = 110;

#define x first
#define y second
typedef pair<int,int> PII;

typedef long long LL;
const LL INF = 1e13;
int n,k,a[N][N];
LL f[N][N],res;
PII pre[N][N];
vector<LL> value[N];

int main()
{
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= i; j++)
			cin >> a[i][j];
	
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= i + 1; j++)
			f[i][j] = -INF;
	
	f[1][1] = a[1][1];	
	for(int i = 2; i <= n; i++)
		for(int j = 1; j <= i; j++)
		{
			if(f[i][j] < f[i - 1][j - 1] + a[i][j])
			{
				f[i][j] = f[i - 1][j - 1] + a[i][j];
				pre[i][j] = {i - 1,j - 1};
			}
			if(f[i][j] < f[i - 1][j] + a[i][j])
			{
				f[i][j] = f[i - 1][j] + a[i][j];
				pre[i][j] = {i - 1,j};
			}
		//	if(i == 2) cout << pre[i][j].x << " " << pre[i][j].y << endl;
		}
	
	//记录下打到最后一行的路经上的值 
	for(int j = 1; j <= n; j++)
	{
		int x = n, y = j;
		//cout << j << endl;
		while(x > 1)
		{
			value[j].push_back(a[x][y]);
		//	cout << x << " " << y << endl;
			PII t = pre[x][y];
			x = t.x, y = t.y;
		}
//		cout << x << " " << y << endl;
//		cout << endl;
		value[j].push_back(a[x][y]);
		sort(value[j].begin(),value[j].end(),greater<LL>());
	}
	 
	//再使用魔法
	for(int j = 1; j <= n; j++)
	{
		LL temp = 0;
	//	for(int i = 0; i < value[j].size(); i++) cout << value[j][i] << " ";
	//	cout << endl;
		for(int i = 0; i < k && i < n && value[j][i] > 0; i++) value[j][i] *= 3;
		for(int i = 0; i < value[j].size(); i++)  temp += value[j][i];
		res = max(res,temp);
	}		
	
	cout << res;
	
	return 0;
}