分数: 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