#include<bits/stdc++.h>
using namespace std;
int n,k,a[105][105],f[105][105],ans,w,y,z,x[105];
queue<int> l[105][105];
bool cmp(int x,int y){
	return x>y;
}
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=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
			l[i][j]=max(l[i-1][j],l[i-1][j-1]);
			l[i][j].push(a[i][j]);
        }
    }
	
	for(int i=1;i<=n;i++){
		if(f[n][i]>ans){
			ans=f[n][i];
			w=i;
		}
	}
	int cnt=0;
	while(l[n][w].size()){
		z=l[n][w].front();
		x[++cnt]=z;
		l[n][w].pop();
	}
	sort(x+1,x+cnt+1,cmp);
	ans=0;
	for(int i=1;i<=cnt;i++){
		if(k){
			ans+=x[i]*3;
			k--;
        }
		else  ans+=x[i];
	}
	cout<<ans;
	return 0;
}