题目描述

存在变量 $x$，初始时 $x = 0$。给定 $n$ 次操作必须按顺序进行，存在两种操作：

• 1 y 表示 $x \leftarrow y$，即将 $x$ 赋值为 $y$。
• 2 y 表示 $x \leftarrow x + y$，即将 $x$ 的值增加 $y$。

你可以从中删除不超过 $k$ 个操作，要求最大化操作后的 $x$，输出最大值。

输入格式

第一行输入 $N$ $K$

接下来 $N$ 行每行两个数字 $t_i,y_i$

输出格式

输出一个整数代表答案

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 解释

如果跳过 $5$ 操作， $x$ 变为 $0 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3$ ，因此 $x$ 的结果是 $3$ 。这就是最大值。

提示

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