B - チーム編成 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は、プログラミングコンテストに出場するチームの監督をしています。

今回の大会では、N 人の選手が候補として集まりました。各選手には 1 から N までの番号が付けられており、選手 i の実力値は A_i です。

大会のルールとして、チームはちょうど K 人で編成する必要があります。基本的には実力値の高い順にメンバーを選びたいのですが、一つ特別な事情があります。

青木君は高橋君の幼馴染であり、候補選手の一人として参加しています。青木君の選手番号は T です。高橋君は青木君を必ずチームに入れると約束しているため、以下のようなメンバー選出方式を取ることにしました：

  1. まず、青木君（選手 T）を必ずチームメンバーに含める。
  2. 残りの K - 1 人は、青木君を除いた N - 1 人の候補選手の中から、実力値の高い順に K - 1 人を選ぶ。ただし K = 1 の場合、青木君のみでチームを編成する。

このルールで選出された K 人の実力値の合計を求めてください。

なお、実力値が等しい選手が複数いて選出の境界にいる場合、どの選手を選んでも実力値の合計は同じになるため、答えは一意に定まります。

制約

  • 1 \leq K \leq N \leq 2 \times 10^5
  • 1 \leq T \leq N
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N K T
A_1 A_2 \ldots A_N
  • 1 行目には、候補選手の人数を表す整数 N、チームの人数を表す整数 K、青木君の選手番号を表す整数 T が、スペース区切りで与えられる。
  • 2 行目には、各選手の実力値を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

選出された K 人の実力値の合計を 1 行で出力してください。

入力例 1

5 3 2
10 5 8 3 7

出力例 1

23

入力例 2

7 4 5
100 250 180 90 120 300 75

出力例 2

850

入力例 3

10 5 7
500000000 300000000 800000000 150000000 600000000 450000000 200000000 900000000 350000000 700000000

出力例 3

3200000000

Score : 300 pts

Problem Statement

Takahashi is the coach of a team competing in a programming contest.

For this tournament, N players have gathered as candidates. Each player is assigned a number from 1 to N, and the skill value of player i is A_i.

According to the tournament rules, a team must consist of exactly K members. Basically, Takahashi wants to select members in descending order of skill value, but there is one special circumstance.

Aoki is Takahashi's childhood friend and is participating as one of the candidate players. Aoki's player number is T. Since Takahashi has promised to include Aoki on the team, he decides to use the following member selection method:

  1. First, Aoki (player T) is always included as a team member.
  2. The remaining K - 1 members are selected from the N - 1 candidate players (excluding Aoki) by choosing the K - 1 players with the highest skill values. However, if K = 1, the team consists of only Aoki.

Find the total skill value of the K members selected under this rule.

Note that if there are multiple players with equal skill values at the selection boundary, the total skill value is the same regardless of which players are chosen, so the answer is uniquely determined.

Constraints

  • 1 \leq K \leq N \leq 2 \times 10^5
  • 1 \leq T \leq N
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers

Input

N K T
A_1 A_2 \ldots A_N
  • The first line contains three space-separated integers: N representing the number of candidate players, K representing the team size, and T representing Aoki's player number.
  • The second line contains space-separated integers A_1, A_2, \ldots, A_N representing the skill values of each player.

Output

Print the total skill value of the selected K members on a single line.

Sample Input 1

5 3 2
10 5 8 3 7

Sample Output 1

23

Sample Input 2

7 4 5
100 250 180 90 120 300 75

Sample Output 2

850

Sample Input 3

10 5 7
500000000 300000000 800000000 150000000 600000000 450000000 200000000 900000000 350000000 700000000

Sample Output 3

3200000000