This problem can be solved with Alien DP (Dynamic Programming).
For the explanation of Alien DP, please also refer to the official editorial of ABC218-H.

We will collectively refer to beauty, tastiness, and popularity as category. The problem can be rephrased as follows:

Among \(3K\) pairs of (cake, category), pick \(2K\) pairs to maximize the sum of the corresponding values, subject to:

– Each cake can be chosen at most once. - Each category is chosen an even number of times.

When we calculate the price of given \(K\) pairs of cakes, the pairs of (cake, category) that are used to calculate the price satisfy the two conditions above, so the sum mentioned above is greater than or equal to the maximum possible total price of pairs of cakes.
Conversely, if a set of chosen pairs satisfy the conditions above, one can pair cakes associated to the same category so that the total price of the pairs of the cakes is greater than or equal to the sum described above.
Therefore, the answers to the original and rephrased problem are the same. From now on, we will consider solving the new version.

More generally, for \(i=0.1.,\ldots, \lfloor\frac{N}{2}\rfloor\), let \(M_i\) be the maximum possible total values corresponding to \(2i\) pairs chosen subject to the two conditions above.

Here, \(M_i\) is concave; specifically, \(M_i-M_{i-1}\geq M_{i+1}-M_i\) for all \(1\leq i\leq \lfloor\frac{N}{2}\rfloor-1\).

Consider the following question.

In addition to \(N\) and \((X_i,Y_i,Z_i)\) \((1\leq i\leq N)\), you are also given a real number \(c\). Pick an even number of elements among the pairs of (cake, category) to maximize the sum of “(the corresponding value) \(\bf{-c}\)” subject to:

• Each cake can be chosen at most once.
• Each category is chosen an even number of times.

When \(2k\) elements are chosen, the sum of “(the corresponding value) \(-c\)” equals the sum of the prices of the pairs, minus \(2kc\). Thus, the answer to the question above \(f(c)\) can be represented using \(M_i\) as

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

Comparing adjacent indices \(i\), we have \(M_i-2ic\leq M_{i+1}-2(i+1)c \Leftrightarrow c\leq \frac{1}{2}(M_{i+1}-M_i)\). By the aforementioned concavity, we have \(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}\), so it takes on the maximum value at \(i=\lfloor\frac{N}{2}\rfloor\) if \(c\leq \frac{1}{2}(M_{\lfloor\frac{N}{2}\rfloor}-M_{\lfloor\frac{N}{2}\rfloor-1})\), at \(i=0\) if \(c\geq \frac{1}{2}(M_{1}-M_{0})\), and otherwise, there exists \(1\leq i_0\leq \lfloor\frac{N}{2}\rfloor-1\) satisfying \(\frac{1}{2}(M_{i_0+1}-M_{i_0})\leq c\leq \frac{1}{2}(M_{i_0}-M_{i_0-1})\), such that it takes on the maximum value at \(i=i_0\).

Therefore, if we can find some \(c\) that gives the maximum value at \(i=k\) and the answer \(X_c\) for that \(c\), we can also find \(M_k\) by \(M_k=X_c+2kc\).

Now, let us consider how to find such \(c\) and the answer \(f(c)\) for that.

Here, since \(M_{i+1}-M_i\) is an integer between \(0\) and \(2\times 10^9\) (inclusive), it is sufficient to consider half-integers \(c\) between \(0\) and \(10^9\). (There is always such \(c\) among them.) Here, a half-integer is a value that can be represented as \(\frac{n}{2}\) for some integer \(n\).

Since there is a finite number of candidates for \(c\), if we can find not only the answer for a given \(c\) but also an index \(i\) that achieves it, we can do a binary search with respect to \(c\). Specifically, if the index \(i_0\) such that \(f(c)=M_{i_0}-2i_0c\) satisfies \(i_0<k\), then \(c\geq \frac{1}{2}(M_{i_0+1}-M_{i_0})\geq \frac{1}{2}(M_{k+1}-M_{k})\), and thus \(c\) must be less than that; if \(i_0>k\), then \(c\leq \frac{1}{2}(M_{i_0}-M_{i_0-1})\geq \frac{1}{2}(M_{k}-M_{k-1})\), and thus \(c\) must be greater than that.

Therefore it is sufficient to, given a specific \(c\), find the answer to the following question as well as the number of pairs that achieves it.
This can be done with DP (Dynamic Programming). Specifically, we can define \(dp[i][f_X][f_Y][f_Z]\) as the maximum “sum of (the value corresponding to that pair \(-c\)) over the chosen pairs” and “the number of pairs chosen to achieve the maximum” among all the ways to choose pairs of (cake, category) from cakes \(1\) through \(i\) so that the parities of the numbers of chosen pairs for the categories are \(p_X,p_Y,p_Z\). The values \(dp[i][f_X][f_Y][f_Z]\) can be computed from \(dp[i-1][f'_X][f'_Y][f'_Z]\) by considering both cases, one of choosing a pair of cake \(i\) and a category and the other of not choosing a pair containing cake \(i\), in \(O(N)\) time (with a rather large constant factor).

Hence, the answer for a given \(c\) and the number of pairs that achieves it can be found in \(O(N)\) time, so the problem can be solved in a total of \(O(N\log \max(X_i,Y_i,Z_i))\) time, which is fast enough.
Therefore, the problem has been solved.

Alternatively, we can start with greedy algorithm and compute the delta to find the true answer. Please refer to user’s editorials (currently available only in Japanese).

Sample code in 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;
}