三序列构造

题目描述

给出 3 * n 个数 x_i，要求构造三个长度均为 n 的序列：

a_1, a_2, ..., a_n
b_1, b_2, ..., b_n
c_1, c_2, ..., c_n

需要满足：

1. 1 到 3 * n 的每个下标，都在三个序列中的某一个中出现一次且仅一次；
2. 最大化下面的值：

S = sum((x[a_i] - x[b_i]) * x[c_i])

其中求和范围为 i = 1, 2, ..., n。

请输出最大的 S。

本题包含多组数据。

输入格式

第一行包含两个整数 T 和 n，其中：

• T 表示数据组数；
• n 的含义如题目描述。

接下来 T 行，每行包含 3 * n 个整数，表示 x_i。

输出格式

输出共 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 组测试数据；
• 所有 x_i <= 1000。

来源

2011 福建集训