分数: 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