忽略操作

题目描述

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
⋮
t_N y_N

输出格式

输出答案。

样例

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

3

若他跳过第 $5$ 个操作,则 $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

数据范围

• $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)$
• 输入中的所有值都是整数。