Hide

Problem C
ICPC Team Selection

The coach of Nha Trang University, Mr. Van, has just organized a contest to form its ICPC teams. There were students participating in the contest. The ith student scored Pi in the contest.

The coach wants to form N different teams (each team has 3 students) to take part in the regional contest based on the results from this contest. In his experience, the performance of a team is usually equal to the median of team members’ individual results (i.e. the result of the second-best student).

The coach wants to maximize S – the sum of his N teams’ performance. Your task is to calculate S.

Input

The input consists of several datasets. The first line of the input contains the number of datasets which is a positive integer and is not greater than 20. The following lines describe the datasets.

Each dataset is described by the following lines:

  • The first line contains a positive integer N (N100).

  • The second line contains 3N positive integers P1,P2,,P3N (Pi100).

Output

For each dataset, output the value S.

Explanation for the Sample Dataset

One way to form two teams is:

  • Team 1: student 1, student 2, student 3;

  • Team 2: student 4, student 5, student 6.

Sample Input 1 Sample Output 1
1
2
8 8 6 9 10 9
17
Hide

Please log in to submit a solution to this problem

Log in