题目描述

存在变量 $x$，初始时 $x = 0$。给定 $n$ 次操作按顺序进行，存在两种操作，每种操作表示为 $\{t_i,y_i\}$ ：

• 1 y 表示 $x = y$
• 2 y 表示 $x = x + y$

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

输入格式

第一行输入两个整数 $n,k$ 。

接下来 $n$ 行，每行输入两个整数 $t_i,y_i$ 。

输出格式

输出可能的最大答案。

样例 #1

样例输入 #1

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

样例输出 #1

3

跳过第五次操作， $x$ 最后是 $3$ ，这是最大的可能性。

样例 #2

样例输入 #2

1 0
2 -1000000000

样例输出 #2

-1000000000

样例 #3

样例输入 #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

提示

对于 $100\%$ 的数据：

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