[ABC249F] Ignore Operations
题意翻译
存在变量 $ x $，初始时 $ x = 0 $。给定 $ n $ 次操作按序进行，存在两种，`1 y` 表示 $ x \leftarrow y $，`2 y` 表示 $ x \leftarrow x + y $，你可以从中删除不超过 $ k $ 个操作，要求最大化操作后的 $ x $，输出最大值。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc249/tasks/abc249_f
高橋君は整数 $ 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 $ で置き換える。
高橋君は $ 0 $ 個以上 $ K $ 個以下の好きな個数の操作を無視することができます。残った操作を一度ずつ順序を変えずに行ったとき、最終的な $ x $ の値としてあり得る最大値を求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ 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输入样例 #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说明
### 制約
- $ 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) $
- 入力は全て整数
### Sample Explanation 1
$ 5 $ 個目の操作を無視すると、$ x $ は $ 0\ \rightarrow\ 4\ \rightarrow\ 1\ \rightarrow\ 2\ \rightarrow\ 3 $ と変化し、最終的な $ x $ の値は $ 3 $ となります。これが最大です。