F - 忽略操作

分数：500分

问题描述

高桥有一个整数$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$。

高桥可以跳过$0$到$K$之间（包括$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$

输出

输出答案。

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

3

如果他跳过第五个操作，$x$的变化如下：$0 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3$，所以$x$的结果为$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