分数: 500 点
问题陈述
有 N 项目。
其中每一个都是拉环罐、普通罐或开罐器之一。
的 i- 第一项由整数对描述 (T_i, X_i) 如下:
- If T_i = 0, i- 第一项是拉环罐;如果你得到它,你就会得到幸福 X_i.
- If T_i = 1, i- 第一项是普通罐头;如果你得到它并使用开罐器来对付它,你会得到幸福 X_i.
- If T_i = 2, i- 第一项是开罐器;它最多可以用来对抗 X_i 罐头。
找出你通过获得获得的最大总幸福感 M 项目超出 N.
约束
- 1 \leq M \leq N \leq 2 \times 10^5
- T_i is 0, 1,或 2.
- 1 \leq X_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M T_1 X_1 T_2 X_2 \vdots T_N X_N
输出
将答案打印为整数。
示例输入 1
8 4 0 6 0 6 1 3 1 5 1 15 2 1 2 10 2 100
示例输出 1
27
如果您获得 1-st, 2-nd, 5-th,以及 7- 第一项,并使用 7- 第一项(开罐器) 5第一项,您将获得的幸福 6 + 6 + 15 = 27.
没有办法获得物品来获得幸福 28 或更大,但你仍然可以获得 27 通过获取 6-th 或 8- 第一项而不是 7- 上述组合中的第一个。
示例输入 2
5 5 1 5 1 5 1 5 1 5 1 5
示例输出 2
0
示例输入 3
12 6 2 2 0 1 0 9 1 3 1 5 1 3 0 4 2 1 1 8 2 1 0 1 0 4
示例输出 3
30