rt

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int n,k;
const int N=110;
ll max(ll _a,ll _b){ return _a>_b?_a:_b; }
ll a[N][N],f[N][N][N];
int main(){
	cin>>n>>k; k=min(k,n);
	for(int i=0;i<N;i++)
	  for(int j=0;j<N;j++)
	    for(int kk=0;kk<=k;kk++) 
		  f[i][j][kk]=-1e18;
	
	for(int i=1;i<=n;i++) 
	  for(int j=1;j<=i;j++) cin>>a[i][j];
	for(int i=1;i<=n;i++) f[n][i][0]=a[n][i],f[n][i][1]=a[n][i]*3ll;
	
	for(int i=n-1;i>=1;i--){
		
	  for(int j=1;j<=i;j++){
	    for(int kk=0;kk<=k;kk++){
	    	if(kk>0) {
	    		f[i][j][kk]=max(f[i][j][kk],max(f[i+1][j][kk-1],f[i+1][j+1][kk-1])+a[i][j]*3ll);
			//	cout<<f[i][j][kk]<<' ';
			}
			f[i][j][kk]=max(f[i][j][kk],max(f[i+1][j][kk],f[i+1][j+1][kk])+a[i][j]);
		//	cout<<f[i][j][kk]<<	' ';
		}
//		cout<<"\n\n\n";
	  }
//	  cout<<"\n\n\n\n";
	}
	ll ans=-1e18;	
	for(int i=0;i<=n;i++) {
		ans=max(ans,f[1][1][i]);
	//	cout<<f[1][1][i]<<' ';
	}
	cout<<ans;
	return 0;
}