题目描述

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$ 的最大可能最终值。

约束条件

• $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