Problem AQ
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 $i^\textrm {th}$ student scored $P_ i$ 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$ $(N \le 100)$.
-
The second line contains $3N$ positive integers $P_1, P_2, \ldots , P_{3N}$ $(P_ i \le 100)$.
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 |
