Problem K
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$.


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


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
8 8 6 9 10 9

Please log in to submit a solution to this problem

Log in