#P17005. [SGU485] Arrays

[SGU485] Arrays

题目描述

给定一个长度为 3N3N 的整数序列 X1,X2,…,X3NX_1,X_2,\dots,X_{3N}。

你需要构造三个长度均为 NN 的下标序列:

  • A1,A2,…,ANA_1,A_2,\dots,A_N;
  • B1,B2,…,BNB_1,B_2,\dots,B_N;
  • C1,C2,…,CNC_1,C_2,\dots,C_N。

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

定义

S=∑i=1N(XAi−XBi)⋅XCiS=\sum_{i=1}^{N}(X_{A_i}-X_{B_i})\cdot X_{C_i}。

请你求出 SS 的最大可能值。

输入格式

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

T,NT,N 满足下表中的限制:

NN 的范围 TT 的范围
1≤N≤101\le N\le10 1≤T≤10001\le T\le1000
11≤N≤1511\le N\le15 1≤T≤1001\le T\le100
16≤N≤2016\le N\le20 1≤T≤101\le T\le10
21≤N≤2521\le N\le25 T=1T=1

接下来 TT 行,每行包含 3N3N 个整数 X1,X2,…,X3NX_1,X_2,\dots,X_{3N},描述一个测试用例。

对于所有 ii,均有 0≤Xi≤10000\le X_i\le1000。

输出格式

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

样例

1 2
4 1 8 2 0 5
46

样例说明

可以取

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

此时

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