题目描述
给出 3×n 个数 xi,要求构造三个长度为 n 的序列 ai,bi,ci,使得满足下列条件:1 到 3×n 的每个数都在三序列中的某个出现一次。
求 S=∑in(xai−xbi)×xci 最大。
输入格式
第一行包含两个数 T 和 n,T 是数据组数,n 如题目描述。
接下来 T 行,每行包含 3×n 个数,表示 xi。
输出格式
输出包含 T 行,每行输出最大的 S。
样例输入
1 2
4 1 8 2 0 5
样例输出
46
数据规模与约定
对于 1≤n≤10,有不超过 1000 组数据;
对于 11≤n≤15,又不超过 100 组数据;
对于 16≤n≤20 ,有不超过 10 组数据;
对于 21≤n≤25,仅有 1 组数据。
所有 xi≤1000。
来源
2011 福建集训