Ignore Operations

题目描述

Takahashi 有一个整数 $x$。 最初，$x = 0$。 有 $N$ 个操作。 第 $i$ 个操作 $(1 \leq i \leq N)$ 由两个整数 $t_i$ 和 $y_i$ 表示，如下：

如果 $t_i = 1$，将 $x$ 置为 $y_i$。 如果 $t_i = 2$，将 $x$ 置为 $x + y_i$。

Takahashi 可以跳过任意数量在 $0$ 到 $K$（含）之间的操作。 在他对剩下的操作按原顺序各执行一次的情况下，求 $x$ 最终可能的最大值。

输入格式

输入按下面的格式由标准输入给出： $N$ $K$ $t_1$ $y_1$ $\vdots$ $t_N$ $y_N$

输出格式

输出答案。

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

3

1 0
2 -1000000000

-1000000000

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

15

提示

$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)$ 输入中的所有值都是整数。如果他跳过第 $5$ 个操作，$x$ 的变化为 $0 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3$，所以 $x$ 最终为 $3$。 这是最大值。

标签: AtCoder|abc249F

来源

AtCoder|abc249F