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 (X 1, X 2, ·s, X N). Create three sequences (A 1, A 2, ·s, A N), (B 1, B 2, ·s, B N) and (C 1, C 2, ·s, C N) such that:
  • each of the integers from 1 to 3· N belongs to exactly one of the sequences A, B or C;
  • the value of 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).