题目描述

给出 $3\times n$ 个数 $x_i$，要求构造三个长度为 $n$ 的序列 ${a_i}, {b_i}, {c_i}$，使得满足下列条件：$1$ 到 $3 \times n$ 的每个数都在三序列中的某个出现一次。

求 $S = \sum_i ^ n (x_{a_i} - x_{b_i}) \times x_{c_i}$ 最大。

输入格式

第一行包含两个数 $T$ 和 $n$，$T$ 是数据组数，$n$ 如题目描述。

接下来 $T$ 行，每行包含 $3\times n$ 个数，表示 $x_i$。

输出格式

输出包含 $T$ 行，每行输出最大的 $S$。

样例输入

1 2
4 1 8 2 0 5

样例输出

46

数据规模与约定

对于 $1\le n\le10$，有不超过 $1000$ 组数据；

对于 $11 \le n \le 15$，又不超过 $100$ 组数据；

对于 $16 \le n \le 20$ ，有不超过 $10$ 组数据；

对于 $21\le n \le 25$，仅有 $1$ 组数据。

所有 $x_i\le 1000$。

来源

2011 福建集训