#include<bits/stdc++.h>
using namespace std;
long long n,k,a[105][105];
long long f[105][105][5055],ans=-3e9;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=i+1;j++)
	for(int o=0;o<=k;o++)f[i][j][o]=-3e9;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=i;j++){
		cin>>a[i][j];
		for(int o=0;o<=k&&o<=i;o++){
			if(o==0)f[i][j][0]=max(f[i-1][j][0],f[i-1][j-1][0])+a[i][j];
			else {
				long long mx=max(f[i-1][j][o],f[i-1][j-1][o])+a[i][j];
				f[i][j][o]=max(mx,max(f[i-1][j][o-1],f[i-1][j-1][o-1])+3*a[i][j]);
			}
		}
	}
	k=min(k,n);
	for(int j=1;j<=n;j++)
	for(int o=0;o<=k;o++)ans=max(ans,f[n][j][o]);
	cout<<ans<<endl;
	return 0;
}