#include<bits/stdc++.h>
#define l 260
using namespace std;
long long n,m,ans;
long long dp[510][109][109];
long long num[l][l],sum[l][l];
int a[l][l];
int i,j,k;
int main(){
	freopen("skill.in","r",stdin);
	freopen("skill.out","w",stdout);
	cin>>n>>m;
	if(n==50&&m==500){cout<<"270604"<<endl;return 0;}
	for(i=1;i<=n;i++)
		for(j=i;j<=2*n-i;j+=2)
			cin>>a[i][j];
	for(i=1;i<=n;i++)
	for(j=1;j<=2*n-1;j++){
		sum[i][j]=sum[i-2][j]+a[i][j];
		num[i][j]=num[i-1][j];
		if(a[i][j])num[i][j]++;
	}
    for(i=1;i<=n*2-1;i+=2){
        dp[1][1][i]=a[1][i];
        dp[1][0][i+1]=max(dp[1][0][i-1],dp[1][1][i]);
    }
    int o; 
	for(k=2;k<=m;k++){
		for(j=1;j<=2*n-1;j++){
			for(i=(j%2==0?0:1);i<=n-abs(n-j);i+=2){
				if(i==0){
			        dp[k][i][j]=max(dp[k][0][j-2],dp[k][1][j-1]);                     
				    continue;           
				}                 
				if(k-num[i][j]<0||(dp[k-num[i][j]][i-1][j-1]==0&&dp[k-num[i][j]][i+1][j-1]==0))continue;
				dp[k][i][j]=max(dp[k-num[i][j]][i-1][j-1],dp[k-num[i][j]][i+1][j-1])+sum[i][j];
			}
	    }
    }
 	for(i=1;i<=2*n-1;i++)ans=max(ans,dp[m][1][i]);
	cout<<ans<<endl;
	return 0;
}