← 返回题目列表

AtCoder · abc249_f

I. 忽略操作

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

分数: 500 点

问题陈述

高桥有一个整数 x。 最初, x = 0.

有 N 操作。 的 i第次操作 (1 \leq i \leq N) 由两个整数表示 t_i 和 y_i 如下:

  • If t_i = 1,替换 x 与 y_i.
  • If t_i = 2,替换 x 与 x + y_i.

高桥可以跳过之间的任何数字 0 和 K (含)的操作。 当他在不改变顺序的情况下将剩余的操作各执行一次时,找到最终可能的最大值 x.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq K \leq N
  • t_i \in \{1,2\} \, (1 \leq i \leq N)
  • |y_i| \leq 10^9 \, (1 \leq i \leq N)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
t_1 y_1
\vdots
t_N y_N

输出

打印答案。


示例输入 1

5 1
2 4
2 -3
1 2
2 1
2 -3

示例输出 1

3

如果他跳过 5第次操作, x 更改为 0 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3,所以 x 结果 3。 这是最大值。


示例输入 2

1 0
2 -1000000000

示例输出 2

-1000000000

示例输入 3

10 3
2 3
2 -1
1 4
2 -1
2 5
2 -9
2 2
1 -6
2 5
2 -3

示例输出 3

15