C - Team Formation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は、プログラミングコンテストに出場するチームを編成する担当者です。

高橋君の所属するサークルには N 人のメンバーがおり、各メンバーは 1 から N までの番号で識別されています。メンバー i のコンテスト出場経験の有無は値 H_i で表され、H_i = 1 のとき経験者、H_i = 0 のとき初心者です。また、メンバー i のプログラミングスキルは値 P_i で表されます。

高橋君は、コンテストに出場するために N 人の中から K 人のメンバーを重複なく選んでチームを編成したいと考えています。ただし、コンテストのルールにより、選ばれた K 人の中に経験者がちょうど M 人、初心者がちょうど K - M 人含まれている必要があります。

チームの総合力は、選ばれた K 人のメンバーのスキル値 P_i の合計で評価されます。

条件を満たすようにメンバーを選んだとき、チームの総合力の最大値を求めてください。条件を満たす選び方が存在しない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 0 \leq M \leq K
  • H_i \in \{0, 1\} (1 \leq i \leq N)
  • 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N K M
H_1 P_1
H_2 P_2
\vdots
H_N P_N
  • 1 行目には、メンバーの総数 N、選ぶメンバーの人数 K、必要な経験者の人数 M がスペース区切りで与えられる。
  • 続く N 行のうち i 行目 (1 \leq i \leq N) には、メンバー i の経験の有無を表す H_i とスキル値 P_i がスペース区切りで与えられる。

出力

条件を満たすようにメンバーを選んだときのチームの総合力（スキル値の合計）の最大値を 1 行で出力せよ。条件を満たす選び方が存在しない場合は -1 を出力せよ。

入力例 1

5 3 1
1 100
0 80
0 90
1 50
0 70

出力例 1

270

入力例 2

6 4 2
1 500
0 300
1 400
0 600
1 200
0 350

出力例 2

1850

入力例 3

10 5 3
1 1000000000
0 999999999
1 800000000
0 750000000
1 600000000
0 500000000
1 400000000
0 300000000
0 200000000
0 100000000

出力例 3

4149999999

Score : 300 pts

Problem Statement

Takahashi is in charge of forming a team to participate in a programming contest.

The club Takahashi belongs to has N members, and each member is identified by a number from 1 to N. Whether member i has contest experience is represented by the value H_i: H_i = 1 means experienced, and H_i = 0 means beginner. Additionally, member i's programming skill is represented by the value P_i.

Takahashi wants to select K members from the N members (without duplicates) to form a team for the contest. However, due to the contest rules, exactly M of the selected K members must be experienced, and exactly K - M must be beginners.

The team's overall strength is evaluated as the sum of the skill values P_i of the selected K members.

Find the maximum possible overall strength of the team when members are selected to satisfy the conditions. If no valid selection exists, output -1.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 0 \leq M \leq K
  • H_i \in \{0, 1\} (1 \leq i \leq N)
  • 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers

Input

N K M
H_1 P_1
H_2 P_2
\vdots
H_N P_N
  • The first line contains the total number of members N, the number of members to select K, and the required number of experienced members M, separated by spaces.
  • The following N lines, where the i-th line (1 \leq i \leq N) contains H_i representing whether member i is experienced and their skill value P_i, separated by a space.

Output

Output in one line the maximum overall team strength (sum of skill values) when members are selected to satisfy the conditions. If no valid selection exists, output -1.

Sample Input 1

5 3 1
1 100
0 80
0 90
1 50
0 70

Sample Output 1

270

Sample Input 2

6 4 2
1 500
0 300
1 400
0 600
1 200
0 350

Sample Output 2

1850

Sample Input 3

10 5 3
1 1000000000
0 999999999
1 800000000
0 750000000
1 600000000
0 500000000
1 400000000
0 300000000
0 200000000
0 100000000

Sample Output 3

4149999999