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_{3· 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).