485. Arrays
Time limit per test: 1.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



You are given a sequence of 3· N integers (X1, X2, ·s, X3· N). Create three sequences (A1, A2, ·s, AN), (B1, B2, ·s, BN) and (C1, C2, ·s, CN) such that:


each of the integers from 1 to 3· N belongs to exactly one of the sequences A, B or C;

and the value of:

SUM from i=1 to N (Ai - Bi) * Ci 

is the largest possible.


Input

Constraints on N	Constraints on T
1 ≤ N ≤ 10	1 ≤ T ≤ 1000
11 ≤ N ≤ 15	1 ≤ T ≤ 100
16 ≤ N ≤ 20	1 ≤ T ≤ 10
21 ≤ N ≤ 25	T = 1

The input file contains T test cases, all having the same value of N. The first line of the input file contains the integers T and N, constrained as shown in the adjacent table. Each of the following T lines describes one test case and contains 3· N integers, the members of the sequence X. All these values are in the range from 0 to 1000.

Output
The output file should consist of T lines. Each line should contain the largest possible value of S for the corresponding test case from the input file.

Example(s)
sample input
sample output
1 2
4 1 8 2 0 5
46



Note. The maximal value is attained by taking A = (1, 3), B = (2, 5), C = (4, 6).

