问题描述

高桥君的寒假有 $N$ 天。他正在考虑 $N$ 天的用餐计划。

第 $i$ 天的计划是，如果 $T_i$ 等于 $0$，他计划去吃拉面；如果 $T_i$ 等于 $1$，他计划去餐馆。用餐的美味度为 $A_i$。

高桥君有个 美食等级，初始美食等级为 $0$。如果高桥君在拉面店吃饭，他的美食等级会减少 $1$。如果高桥君在餐馆吃饭，他的美食等级会增加 $1$。

高桥君希望将美食等级保持在 $0$ 到 $K$ 之间。他可以取消 $0$ 个或多个用餐计划，并自己做饭。如果自己做饭，美食等级不会变化，用餐的美味度为 $0$。

请计算高桥君在寒假期间可以获得的最大美食总和。

约束条件

• $1 \leq K \leq N \leq 10^{5}$
• $1 \leq A_i \leq 10^9$
• $T_i$ 的值为 0 或 1
• 输入数据都为整数

输入

输入数据从标准输入中按如下格式给出。

$N$ $K$ $T_1$ $A_1$ : $T_{N}$ $A_{N}$

输出

输出答案。

示例 1

8 2
1 3
1 7
0 2
1 8
1 4
0 6
0 2
0 4

输出示例 1

31

• 第 $1$ 天：自己做饭。美食等级保持为 $0$
• 第 $2$ 天：去餐馆。美食等级变为 $1$
• 第 $3$ 天：去拉面店。美食等级变为 $0$
• 第 $4$ 天：去餐馆。美食等级变为 $1$
• 第 $5$ 天：去餐馆。美食等级变为 $2$
• 第 $6$ 天：去拉面店。美食等级变为 $1$
• 第 $7$ 天：自己做饭。美食等级保持为 $1$
• 第 $8$ 天：去拉面店。美食等级变为 $0$
• 可获得的美食总和为 $7+2+8+4+6+4 = 31$，为最大值。

示例 2

15 3
0 3
1 4
1 5
0 2
0 9
0 11
1 6
1 2
1 6
0 4
1 7
0 4
1 8
1 4
1 9

输出示例 2

73

示例 3

5 3
1 1000000000
0 1000000000
1 1000000000
0 1000000000
1 1000000000

输出示例 3

5000000000

请注意答案可能很大。