配点 : 600 点
問題文
高桥君的寒假有 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
- 请注意,答案可能很大