← 返回题目列表

AtCoder · awc0012_c

C. 团队组建

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥负责组队参加编程比赛。

高桥所属俱乐部有 N 成员,每个成员均由以下数字标识 1 to N。是否会员 i 有比赛经验值表示 H_i: H_i = 1 表示经验丰富,并且 H_i = 0 表示初学者。另外,会员 i的编程技能用数值表示 P_i.

高桥想要选择 K 成员来自 N 成员(无重复)组队参加比赛。但由于比赛规则的原因, 所选的 M 所选的 K 成员必须经验丰富且准确 K - M 必须是初学者。

团队的整体实力评估为技能值的总和 P_i 所选的 K 成员。

求当选择满足条件的成员时,团队可能的最大整体实力。如果不存在有效选择,则输出 -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
  • 第一行包含成员总数 N,要选择的成员数量 K,以及所需的经验丰富的成员数量 M,用空格分隔。
  • 以下 N 行,其中 i第行 (1 \leq i \leq N) 包含 H_i 代表是否是会员 i 经验丰富且技能值 P_i,用空格分隔。

输出

在一行中输出当选择满足条件的成员时团队的最大整体实力(技能值之和)。如果不存在有效选择,则输出 -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