この問題は Alien DP を用いて解くことができます。
Alien DP の説明はABC218-Hの公式解説 にも記述されているため、参照してみてください。

以下、綺麗さ、おいしさ、人気度をまとめてカテゴリーと呼ぶことにします。 今回の問題は、次のように言い換えることができます。

合計 \(3N\) 個ある（ケーキ, カテゴリー）の組から、\(2K\) 個を次の条件をともにみたすように選び、対応する値の総和を最大化せよ。

• 各ケーキは高々 \(1\) 回しか選べない
• 各カテゴリーは偶数回ずつ選ばれる。

任意に \(K\) 個のケーキのペアを選んで価格を計算したとき、価格の計算に使われる（ケーキ, カテゴリー）の組は上記の \(2\) つの条件をみたすため、上記の総和はケーキのペアの価格の総和としてあり得る最大値以上になります。
一方で上の条件をみたすとき、同じカテゴリーと組になっているケーキをペアにしていくことで、それらのペアの価格の合計は上記の総和以上になります。
よって、問題の答えと上で言い換えられた問題の答えは一致します。以下、この言い換えられた問題を解くことを考えます。

より一般に、\(i=0.1.,\ldots, \lfloor\frac{N}{2}\rfloor\) について、上記の \(2\) 条件をみたすように（ケーキ, カテゴリー）の組を \(2i\) 個選んだときに総和としてあり得る最大値を \(M_i\) とします。

ここで、\(M_i\) は上に凸です。より具体的には、\(1\leq i\leq \lfloor\frac{N}{2}\rfloor-1\) について、\(M_i-M_{i-1}\geq M_{i+1}-M_i\) が成り立ちます。

次の問題を考えます。

\(N\), \((X_i,Y_i,Z_i)\) \((1\leq i\leq N)\) に加えて、実数 \(c\) が与えられます。 （ケーキ, カテゴリー）の組から、偶数個を次の条件をともにみたすように選び、（対応する値 \(\bf{-c}\)） の 総和を最大化せよ。

• 各ケーキは高々 \(1\) 回しか選べない
• 各カテゴリーは偶数回ずつ選ばれる。

\(2k\) 個選んだとき、（対応する値 \(-c\)）の 総和は、元のケーキのパラメータの総和から\(2kc\) を引いた値となります。 よって、この答え \(f(c)\) は \(M_i\) を用いて、

\[ f(c)=\max_{0\leq i\leq \lfloor\frac{N}{2}\rfloor}(M_i-2ic) \]

と書けます。ここで、隣接する \(2\) つの \(i\) の比較を考えると、\(M_i-2ic\leq M_{i+1}-2(i+1)c \Leftrightarrow c\leq \frac{1}{2}(M_{i+1}-M_i)\) となります。先に述べた凸性から、\(M_1-M_0\geq M_2-M_1\geq \cdots\geq M_{\lfloor\frac{N}{2}\rfloor}-M_{\lfloor\frac{N}{2}\rfloor-1}\) が成り立つことに注意すると、 \(c\leq \frac{1}{2}(M_{\lfloor\frac{N}{2}\rfloor}-M_{\lfloor\frac{N}{2}\rfloor-1})\) ならば \(i=\lfloor\frac{N}{2}\rfloor\) のとき最大に、\(c\geq \frac{1}{2}(M_{1}-M_{0})\) ならば \(i=0\) のとき最大に、それ以外の時、\(\frac{1}{2}(M_{i_0+1}-M_{i_0})\leq c\leq \frac{1}{2}(M_{i_0}-M_{i_0-1})\) をみたす \(1\leq i_0\leq \lfloor\frac{N}{2}\rfloor-1\) が存在し、\(i=i_0\) のとき最大となります。

よって、\(i=k\) のとき最大となるようなある \(c\) と、そのときの答え \(X_c\) が分かれば \(M_k=X_c+2kc\) として、\(M_k\) を求めることができます。

さて、そのような \(c\) およびその時の答え \(f(c)\) を求めることを考えます。

ここで、\(M_{i+1}-M_i\) が \(0\) 以上 \(2\times 10^9\) 以下の整数であることから、\(c\) は \(0\) 以上 \(10^9\) 以下の半整数 の範囲で考えれば十分です。（そのようなものの中に条件をみたす \(c\) が必ず存在します。）ここで、半整数は整数 \(n\) を用いて、\(\frac{n}{2}\) と書ける数全体を表します。

\(c\) が有限な候補の中に存在することから、 \(c\) が与えられた時の答えに加えて、それを達成する \(i\) も分かれば、\(c\) について二分探索を行うことができます。より具体的には、\(f(c)=M_{i_0}-2i_0c\) をみたす \(i_0\) が \(i_0<k\) ならば \(c\geq \frac{1}{2}(M_{i_0+1}-M_{i_0})\geq \frac{1}{2}(M_{k+1}-M_{k})\) より \(c\) はそれ以下の値である必要があり、\(i_0>k\) ならば \(c\leq \frac{1}{2}(M_{i_0}-M_{i_0-1})\geq \frac{1}{2}(M_{k}-M_{k-1})\) より \(c\) はそれ以上の値である必要があることがわかります。

よって、特定の \(c\) が与えられた時、上記の問題の答えおよびそれを達成するペアの個数を高速に求められれば良いです。
これは動的計画法によって求めることができます。具体的には \(dp[i][f_X][f_Y][f_Z]\) を、「ケーキ \(1\)からケーキ \(i\) までの中から（ケーキ, カテゴリ）の組を \(1\) つめの条件をみたすように選んだとき、各カテゴリーが選ばれた組に含まれる数の 偶奇 がそれぞれ \(p_X,p_Y,p_Z\) の条件下における、（選ばれた組に対応する値 \(-c\)）の総和の最大値およびそれを達成するの組の使用数」と定義すれば良いです。\(dp[i][f_X][f_Y][f_Z]\) はケーキ \(i\) と特定のカテゴリーのペアを選ぶ場合、ケーキ \(i\) を含むペアを選ばない場合の両方を考えることで \(dp[i-1][f'_X][f'_Y][f'_Z]\) から求めることができ、\(O(N)\) で求めることができます。（定数倍は少し重めです。）

よって、各 \(c\) に対する問題の答えおよびそれを達成するペアの個数が \(O(N)\) で求まるため、全体で \(O(N\log \max(X_i,Y_i,Z_i))\) でこの問題を解くことができ、十分高速です。
よって、この問題を解くことができました。

他にも貪欲法からの差分を計算する方法もあります。ユーザー解説等をご覧ください。

c++ による実装例:

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

#define pll pair<long long,long long>
#define rep(i, n) for(int i = 0; i < n; ++i)

long long n,k;
long long x[100000][3];

pll solve(int c){
	vector<pll> dp(8,{-((long long)1e18),0LL});
	dp[0]={0LL,0LL};
	rep(i,n){
		vector<pll> dp2=dp;
		rep(j,8){
			rep(k,3){
				pll tmp={dp[j].first+2*x[i][k]-c,dp[j].second+1};
				dp2[j^(1<<k)]=max(dp2[j^(1<<k)],tmp);
			}
		}
		dp=dp2;
	}
	return dp[0];
}

int main(void){
	int t;
	cin>>t;
	rep(_,t){
		cin>>n>>k;
		rep(i,n)cin>>x[i][0]>>x[i][1]>>x[i][2];
		long long l=0,r=1LL<<31;
		while((l+1)<r){
			long long m=(l+r)/2;
			if(solve(m).second>=(2*k))l=m;
			else r=m;
		}
		long long ans=(solve(l).first+2*k*l)/2;
		cout<<ans<<endl;
	}
	return 0;
}