bzoj#P5003. 构造数组

构造数组

题目描述

给出 3×n3\times n 个数 xix_i,要求构造三个长度为 nn 的序列 ai,bi,ci{a_i}, {b_i}, {c_i},使得满足下列条件:113×n3 \times n 的每个数都在三序列中的某个出现一次。

S=in(xaixbi)×xciS = \sum_i ^ n (x_{a_i} - x_{b_i}) \times x_{c_i} 最大。

输入格式

第一行包含两个数 TTnnTT 是数据组数,nn 如题目描述。

接下来 TT 行,每行包含 3×n3\times n 个数,表示 xix_i

输出格式

输出包含 TT 行,每行输出最大的 SS

样例输入

1 2
4 1 8 2 0 5

样例输出

46

数据规模与约定

对于 1n101\le n\le10,有不超过 10001000 组数据;

对于 11n1511 \le n \le 15,又不超过 100100 组数据;

对于 16n2016 \le n \le 20 ,有不超过 1010 组数据;

对于 21n2521\le n \le 25,仅有 11 组数据。

所有 xi1000x_i\le 1000

来源

2011 福建集训