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;
- 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).