#include<queue>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
long n,k;

struct COADA
{
	long tr[1001];
	long l,s;
};
COADA temp;
vector<long>a[1001];
vector<long>b[1001];
vector<long>c[1001];

void read(){
	long i,j,nr;
	scanf("%ld%ld",&n,&k);
	for (i=1;i<=n;i++)
		for (j=1;j<=i;j++) {
			scanf("%ld",&nr);
			a[i].push_back(nr);
		}
}

void rez () {
	long i,s1,lim,s2,s3,j,max=-1,cn;
	queue<COADA>q;
	vector <long> :: iterator it;
	temp.s=temp.l=0;
	memset(temp.tr,0,sizeof(temp.tr));
	cn=n;
	q.push(temp);
	while (!q.empty()) {
		temp=q.front();
		for (i=1;i<=n;i++)
			b[i]=a[i];
		lim=temp.tr[0];
		for (i=1;i<=lim;i++) {
			if (temp.tr[i]==1) {
				for (j=1;j<=n;j++)
					b[j].erase(b[j].begin(),b[j].begin()+1);
				for (j=2;j<=n;j++)
					b[j-1]=b[j];
				b[n].clear();
				n--;
			}
			if (temp.tr[i]==2) {
				b[n].clear();
				n--;
			}
			if (temp.tr[i]==3) {
				for (j=1;j<=n;j++)
					b[j].erase(b[j].end()-1,b[j].end());
				for (j=2;j<=n;j++)
					b[j-1]=b[j];
				b[n].clear();
				n--;
			}
		}
		for (i=1;i<=n;i++)
			c[i]=b[i];
		COADA temp2;
		temp2.l=temp.l+1;
		temp2.s=temp.s;
		memcpy(temp2.tr,temp.tr,sizeof(temp.tr));
		
		temp2.tr[++temp2.tr[0]]=1;
		for (j=1;j<=n;j++)
			temp2.s=temp2.s+b[j].front();
		if (temp2.l==k && temp2.s>max)
			max=temp2.s;
		if (temp2.l<k)
			q.push(temp2);
		
		temp2.tr[temp2.tr[0]]=2;
		temp2.s=temp.s;
		for (it=b[n].begin();it!=b[n].end();++it)
			temp2.s=temp2.s+(*it);
		if (temp2.l==k && temp2.s>max)
			max=temp2.s;
		if (temp2.l<k)
			q.push(temp2);
		
		temp2.tr[temp2.tr[0]]=3;
		temp2.s=temp.s;
		for (j=1;j<=n;j++)
			temp2.s=temp2.s+b[j].back();
		if (temp2.l==k && temp2.s>max)
			max=temp2.s;
		if (temp2.l<k)
			q.push(temp2);
		n=cn;
		q.pop();
	}
	printf("%ld\n",max);
}

int main () {
	freopen("ferma2.in","r",stdin);
	freopen("ferma2.out","w",stdout);
	
	read();
	rez();
	return 0;
}