← 返回题目列表

AtCoder · code_festival_2018_final_f

F. 晚餐计划

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

配点 : 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
  • 请注意,答案可能很大