#include<bits/stdc++.h>
using namespace std;
long long n,k,a[105][105],ans,w,y,z;
struct node{
	int f;
	int l[105];
}x[105][105];
bool cmp(long long x,long long y){
	return x>y;
}
int main(){
	cin>>n>>k;
	for(long long i=1;i<=n;i++)
		for(long long j=1;j<=i;j++)
            cin>>a[i][j];
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=i;j++){
			if(x[i-1][j].f>x[i-1][j-1].f){
				x[i][j].f=x[i-1][j].f+a[i][j];
				for(int k=1;k<i;k++)
					x[i][j].l[k]=x[i-1][j].l[k];
			}else{
				x[i][j].f=x[i-1][j-1].f+a[i][j];
				for(int k=1;k<i;k++)
					x[i][j].l[k]=x[i-1][j-1].l[k];
			}
			x[i][j].l[i]=a[i][j];
        }
    }
	for(long long i=1;i<=n;i++){
		if(x[n][i].f>ans){
			ans=x[n][i].f;
			w=i;
		}
	}
	int q[105];
	for(int i=1;i<=n;i++) q[i]=x[n][w].l[i];
	sort(q+1,q+n+1,cmp);
	ans=0;
	for(long long i=1;i<=n;i++){
        if(q[i]<=0) k=0;
		if(k){
			ans+=q[i]*3;
			k--;
        }
		else ans+=q[i];
	}
	cout<<ans;
	return 0;
}