该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

CMY在卡拉迪亚的野心日益膨胀，他与巴旦尼亚至高王卡拉德加的冲突已近白热化。CMY的目标不仅是王座，更是要向世人证明，他才是那个能让巴丹尼亚实现最大“繁荣度”的唯一领袖。卡拉德加为了打压CMY，故意交给他 $N$ 块新征服的、混乱不堪的封地，并只给了他 $M$ 支皇家卫戍部队的编制。

题目描述

CMY必须从 $N$ 块封地中，恰好选择 $M$ 块，派遣卫戍部队进驻。他的选择将决定他能从这些领地中榨取……呃，是“发展”出多少总繁荣度。每一块封地 $i$ 都由其类型 $T_i$ 和潜力值 $X_i$ 共同描述：

• 如果 $T_i = 0$： 该封地是一座城镇。

  • 它秩序井然，无需额外管理。只要CMY派遣卫戍部队进驻，就能立即获得 $X_i$ 的繁荣度。

• 如果 $T_i = 1$：该封地是一个待开发的村庄。

  • 它拥有巨大的潜力，承诺 $X_i$ 的繁荣度。但它目前法纪混乱，盗匪横行。

  • 如果CMY只派部队进驻，什么也得不到。他必须同时利用“城堡”的管理能力来“激活”它。

• 如果 $T_i = 2$：该封地是一座行政城堡。

  • 它本身不产出任何繁荣度。

  • 如果CMY选择进驻这座城堡，它将提供 $X_i$ 点“行政力”。每 $1$ 点行政力，可以用来“激活” $1$ 个同样被CMY进驻的“待开发的村庄”。

总繁荣度计算如下：

1. 他选择的所有“繁荣的城镇”的 $X_i$ 值总和。

2. 他选择的所有“行政城堡”会提供一个“行政力”总和 $C_{total}$。

3. 他选择的所有“待开发的村庄”中，他可以从中挑选最多 $C_{total}$ 个，来获得它们的 $X_i$ 繁荣度。

请帮助CMY制定一个选择 $M$ 块封地的最佳方案，使得他能获得的总繁荣度最大。

输入格式

第一行输入两个整数 $N$ 和 $M$ ($1 \le M \le N \le 2*10^5$)

接下来 $N$ 行，每行包含两个整数 $T_i$ 和 $X_i$

$T_i$ is $0$, $1$, or $2$.

$1 \leq X_i \leq 10^9$

输出格式

输出一个整数，代表CMY能获得的最大总繁荣度。

样例数据

样例一

输入

5 3
0 10
0 20
1 100
1 50
2 1

输出

120

样例二

输入

5 3
0 10
0 20
1 100
1 50
2 2

输出

170

样例解释

对于样例1：

CMY需要选择3块封地。

• 最优解： 选择 城镇(繁荣20), 村庄(繁荣100), 城堡(行政力1)。

• 分析：

  1. 城堡 提供了 1 点行政力。

  2. 城镇 提供了 20 繁荣度。

  3. 使用 1 点行政力激活村庄， 获得了 100 繁荣度。

• 总计： $20 + 100 = 120$。

对于样例2：

CMY需要选择3块封地。

• 最优解： 选择 村庄(繁荣100), 村庄(繁荣50), 城堡(行政力2)。

• 分析：

  1. 城堡( 提供了 2 点行政力。

  2. 使用这 2 点行政力，分别激活村庄(繁荣100) 和 村庄（繁荣50）。

  3. 获得了 100 + 50 = 150 繁荣度。

• 总计： 150。