A - AtCoder Group Contest Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

AtCoder Group Contestの参加者に 3N 人が参加します。 i 番目の参加者の 強さ は整数 a_i で表されます。 参加者が 3 人 1 組となるようにチームを N 組作ることにしました。1 人の参加者が複数のチームに所属することはできません。

チームの強さはチームメンバーの強さのうち 2 番目に大きい値で表されます。 例えば、強さが 1,5,2 のメンバーからなるチームの強さは 2 になり、強さが 3,2,3 のメンバーからなるチームの強さは 3 になります。

N 組のチームの強さの和としてありうる値のうち、最大の値を求めてください。

制約

  • 1 ≦ N ≦ 10^5
  • 1 ≦ a_i ≦ 10^{9}
  • a_i は整数

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 ... a_{3N}

出力

答えを出力せよ。

入力例 1

2
5 2 8 5 1 5

出力例 1

10

例えば以下のようにチームを作ったとき、チームの強さの和が最大となります。

  • チーム 1：1,4,5 番目の参加者からなる。
  • チーム 2：2,3,6 番目の参加者からなる。

入力例 2

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 2

10000000000

チームの強さの和は非常に大きくなることがあります。

Score : 300 points

Problem Statement

There are 3N participants in AtCoder Group Contest. The strength of the i-th participant is represented by an integer a_i. They will form N teams, each consisting of three participants. No participant may belong to multiple teams.

The strength of a team is defined as the second largest strength among its members. For example, a team of participants of strength 1, 5, 2 has a strength 2, and a team of three participants of strength 3, 2, 3 has a strength 3.

Find the maximum possible sum of the strengths of N teams.

Constraints

  • 1 ≤ N ≤ 10^5
  • 1 ≤ a_i ≤ 10^{9}
  • a_i are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_{3N}

Output

Print the answer.

Sample Input 1

2
5 2 8 5 1 5

Sample Output 1

10

The following is one formation of teams that maximizes the sum of the strengths of teams:

  • Team 1: consists of the first, fourth and fifth participants.
  • Team 2: consists of the second, third and sixth participants.

Sample Input 2

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 2

10000000000

The sum of the strengths can be quite large.