构造数组

时间限制:20s      空间限制:256MB

题目描述

给出3*n个数xi,要求构造三个长度为n的序列aibici,使得满足下列条件:
13*n的每个数都在三个序列中的某个出现一次且仅一次;
S=sum((x[ai]-x[bi])*x[ci])最大。
输出最大的S
多组数据。


输入格式

第一行包含两个数TnT是数据组数,n如题目描述。
接下来T行,每行包含3*n个数,表示xi
 


输出格式

输出包含T行,每行输出最大的S
 


样例输入

1 2
4 1 8 2 0 5

 

样例输出

46
  
 

提示


Data Limit
对于1<=n<=10,有不超过1000组数据;
对于11<=n<=15,又不超过100组数据;
对于16<=n<=20,有不超过10组数据;
对于21<=n<=25,仅有1组数据。
所有xi<=1000。


题目来源

2011福建集训