C++ :

# include <cstdio>
# include <cstring>
# include <algorithm>
# include <iostream>

# define Max(a,b) ((a)>(b)?(a):(b)) 

using namespace std;

const int MAXN = 55;
const int MAXM = 505;

int n,m,ans;
int brick[MAXN][MAXN];
int sum[MAXN][MAXN];
int f[MAXN][MAXM][MAXM];

void init(){
	int i,j,k,p;
	memset(f,-1,sizeof(f));
	scanf("%d%d",&n,&m);
	for(i = 1;i <= n;++i)
		for(j = i;j <= n;++j)
			scanf("%d",&brick[j][i]);
	for(i = 1;i <= n;++i)
		for(j = 1;j <= i;++j)
			sum[i][j] = sum[i][j - 1] + brick[i][j];
	for(i = 0;i <= n;++i) f[i][0][0] = 0;
	for(i = 1;i <= n;++i) f[i][1][1] = brick[i][1];
	for(i = 1;i <= n;++i)
		for(k = 0;k <= i;++k)
			for(j = k;j <= m;++j)
				for(p = k - 1;p <= i;++p)
					if(f[i - 1][j - k][p] != -1){
						f[i][j][k] = Max(f[i][j][k],f[i - 1][j - k][p] + sum[i][k]);
						if(j == m) ans = Max(ans,f[i][j][k]);
					}
	printf("%d",ans);
	return ;					
}

int main(){
	init();
	return 0;
}