题目描述

给定一个长度为 $3N$ 的整数序列 $X_1,X_2,\dots,X_{3N}$。

你需要构造三个长度均为 $N$ 的下标序列：

• $A_1,A_2,\dots,A_N$；
• $B_1,B_2,\dots,B_N$；
• $C_1,C_2,\dots,C_N$。

要求 $1,2,\dots,3N$ 中的每一个整数都恰好出现在三个序列 $A,B,C$ 中的一个位置，也就是说，这三个序列共同构成对全部 $3N$ 个下标的一次划分。

定义

$S=\sum_{i=1}^{N}(X_{A_i}-X_{B_i})\cdot X_{C_i}$。

请你求出 $S$ 的最大可能值。

输入格式

第一行包含两个整数 $T,N$，表示测试用例数以及每个测试用例的参数 $N$。所有测试用例的 $N$ 相同。

$T,N$ 满足下表中的限制：

接下来 $T$ 行，每行包含 $3N$ 个整数 $X_1,X_2,\dots,X_{3N}$，描述一个测试用例。

对于所有 $i$，均有 $0\le X_i\le1000$。

输出格式

对于每个测试用例输出一行一个整数，表示 $S$ 的最大可能值。

样例

1 2
4 1 8 2 0 5

46

样例说明

可以取

• $A=(1,3)$；
• $B=(2,5)$；
• $C=(4,6)$。

此时

$S=(X_1-X_2)X_4+(X_3-X_5)X_6=(4-1)\times2+(8-0)\times5=46$。