题解：AT_abc400_g [ABC400G] Patisserie ABC 3

use itertools::*;
use memoise::*;
use proconio::marker::*;
use proconio::*;
use std::collections::*;
use superslice::Ext;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

const MOD: u64 = 998_244_353;
const INF: i64 = 1 << 50;

fn main() {
    input! {
        t: usize,
    }

    for _ in 0..t {
        input! {
            n: usize,
            k: usize,
            mut xyz: [(i64, i64, i64); n],
        }

        xyz.sort_unstable_by_key(|(x, y, z)| *x.max(y).max(z));
        xyz.reverse();

        // dp[i][t][b]: [0, i) のなかでスルーしたのが t 個で現在の選択の偶奇状況が b
        // であるようなものの最大値
        let mut dp = [[-INF; 8]; 3];
        dp[0][0] = 0;

        for &(x, y, z) in xyz[..2 * k].iter() {
            let mut ep = [[-INF; 8]; 3];
            // x として選択する。
            for t in 0..=2 {
                for b in 0..8 {
                    ep[t][b ^ 1] = ep[t][b ^ 1].max(dp[t][b] + x);
                }
            }
            // y として選択する。
            for t in 0..=2 {
                for b in 0..8 {
                    ep[t][b ^ 2] = ep[t][b ^ 2].max(dp[t][b] + y);
                }
            }
            // z として選択する。
            for t in 0..=2 {
                for b in 0..8 {
                    ep[t][b ^ 4] = ep[t][b ^ 4].max(dp[t][b] + z);
                }
            }
            // 何も選択せずにスルーする。
            for t in 0..2 {
                for b in 0..8 {
                    ep[t + 1][b] = ep[t + 1][b].max(dp[t][b]);
                }
            }

            dp = ep;
        }

        for &(x, y, z) in xyz[2 * k..].iter() {
            let mut ep = [[-INF; 8]; 3];
            // 何も選択せずにスルーする。
            for t in 0..=2 {
                for b in 0..8 {
                    ep[t][b] = ep[t][b].max(dp[t][b]);
                }
            }
            // x として選択する。
            for t in 1..=2 {
                for b in 0..8 {
                    ep[t - 1][b ^ 1] = ep[t - 1][b ^ 1].max(dp[t][b] + x);
                }
            }
            // y として選択する。
            for t in 1..=2 {
                for b in 0..8 {
                    ep[t - 1][b ^ 2] = ep[t - 1][b ^ 2].max(dp[t][b] + y);
                }
            }
            // z として選択する。
            for t in 1..=2 {
                for b in 0..8 {
                    ep[t - 1][b ^ 4] = ep[t - 1][b ^ 4].max(dp[t][b] + z);
                }
            }

            dp = ep;
        }

        println!("{}", dp[0][0]);
    }
}

#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];
}
signed main(){
	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;
	}
}