#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define RE register

inline int read(){
    RE int x=0,t=1;RE char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-'){t=-1;}ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*t;
}

const int N=1e3+7;

int n,k;
LL f[N][N][8];
LL a[N][4];
signed main(){
    n=read(),k=read();
    //memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=3;j++){
            scanf("%lld",&a[i][j]);
        }
    }
    LL res=0;
    for(int i=1;i<=n;i++){
        for(int kk=1;kk<=min(k,i*3/2);kk++){
            for(int j=0;j<8;j++){
                f[i][kk][0]=max(f[i][kk][0],f[i-1][kk][j]);
                //为空情况  xxx/000
                LL list1=a[i-1][1]+a[i][1],list2=a[i-1][2]+a[i][2],list3=a[i-1][3]+a[i][3];
                LL row1=a[i][1]+a[i][2],row2=a[i][2]+a[i][3];

                if(!(j&1)&&(i>1)){//xx0
                    f[i][kk][1]=max(f[i][kk][1],f[i-1][kk-1][j]+list3);//xx1/001
                    if(!((j>>1)&1)&&(kk-2>=0)){//x00
                        f[i][kk][3]=max(f[i][kk][3],f[i][kk-2][j]+list2+list3);//x11/011
                        if(!((j>>2)&1)&&(kk-3>=0))//000
                            f[i][kk][7]=max(f[i][kk][7],f[i][kk-3][j]+list1+list2+list3);//111/111
                    }
                    if(!((j>>2)&1)&&(kk-2>=0)){//0x0
                        f[i][kk][5]=max(f[i][kk][5],f[i][kk-2][j]+list1+list3);//101/101
                    }
                    f[i][kk][7]=max(f[i][kk][7],f[i-1][kk-2][j]+list3+row1);//xx1/111
                    //加一个横的
                }
                if(!((j>>1)&1)&&(i>1)){//x0x
                    f[i][kk][2]=max(f[i][kk][2],f[i-1][kk-1][j]+list2);//x1x/010
                    if(!((j>>2)&1)&&(kk-2>=0)){//00x
                        f[i][kk][6]=max(f[i][kk][6],f[i][kk-2][j]+list1+list2);//11x/110
                    }
                }
                if(!((j>>2)&1)&&(i>1)){//0xx
                    f[i][kk][4]=max(f[i][kk][4],f[i-1][kk-1][j]+list1);//1xx/100
                    f[i][kk][7]=max(f[i][kk][7],f[i-1][kk-2][j]+list1+row2);//1xx/111
                    //加一个横的
                }
                //竖放情况

                //xxx
                f[i][kk][3]=max(f[i][kk][3],f[i-1][kk-1][j]+row2);//xxx/011
                f[i][kk][6]=max(f[i][kk][6],f[i-1][kk-1][j]+row1);//xxx/110
                //横放情况
                res=max(res,f[i][kk][j]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("Line %d:\n",i);
        for(int kk=1;kk<=k;kk++){
            printf("Cost %d:\n",kk);
            for(int j=1;j<8;j++){
                printf("%d%d%d %d\n",j>>2,j>>1&1,j&1,f[i][kk][j]);
            }
        }
    }
    
    printf("%lld\n",res);
    return 0;
}