2016 ACM ICPC Asia Nha Trang Regional Contest Replay


2017-10-15 12:00 UTC

2016 ACM ICPC Asia Nha Trang Regional Contest Replay


2017-10-15 17:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -427 days 12:35:43

Time elapsed


Time remaining


Problem K
ICPC Team Selection

The coach of Nha Trang University – Mr Van has just organized a contest to form its ICPC teams. There was students attending the contest. The $i^{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 this result. In his experience, the performance of a team usually equals to the median of team members’ individual result (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, ..., P_{3N}$ $(P_ i \le 100)$.


For each dataset, write out on one line the value $S$.

Explanation to the sample dataset

One way to form a team 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