#include <bits/stdc++.h>

using namespace std;
#define int long long
const int MAXH = 110;
const int INF  = 0x3f3f3f3f;
const int mod = 1e9 + 7;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int n,k,ans = 0;
int a[MAXH][MAXH];
int dp[MAXH][MAXH][MAXH];
signed main(){
	scanf("%lld%lld",&n,&k);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= i;j++){
            scanf("%lld",&a[i][j]);
        }
    }
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            for(int l = 0;l <= k;l++)
                dp[i][j][l] = 0;
    dp[1][1][0] = a[1][1];
    dp[1][1][1] = a[1][1] * 3;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= i;j++){
            for(int l = 0;l <= k;l++){
                dp[i+1][j][l] = max(dp[i+1][j][l],dp[i][j][l] + a[i+1][j]);
                dp[i+1][j+1][l] = max(dp[i+1][j+1][l],dp[i][j][l] + a[i+1][j+1]);
                dp[i+1][j][l+1] = max(dp[i+1][j][l+1],dp[i][j][l] + a[i+1][j] * 3);
                dp[i+1][j+1][l+1] = max(dp[i+1][j+1][l+1],dp[i][j][l] + a[i+1][j+1] * 3);
            }
        }
    }
    for(int i = 1;i <= n;i++){
        for(int l = 0;l <= k;l++){
            ans = max(ans,dp[n][i][l]);
        }
    }
    printf("%lld\n",ans);
	return 0;
}