← 返回题目列表

AtCoder · abc312_f

I. 罐头和开瓶器

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

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