AT_abc249_f [ABC249F] Ignore Operations

题目描述

高桥君有一个整数 $x$。初始时，$x = 0$。

有 $N$ 次操作。第 $i$ 次操作由整数 $t_i, y_i$ 给出，具体如下：

• 当 $t_i = 1$ 时，用 $y_i$ 替换 $x$。
• 当 $t_i = 2$ 时，用 $x + y_i$ 替换 $x$。

高桥君可以选择忽略 $0$ 个到 $K$ 个操作。对于剩下的操作，按照原顺序依次执行。请你求出最终 $x$ 的可能最大值。

输入格式

输入按以下格式从标准输入给出。

$N$ $K$
$t_1$ $y_1$
$\vdots$
$t_N$ $y_N$

输出格式

请输出最终 $x$ 的最大可能值。

输入输出样例 #1

输入 #1

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

输出 #1

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

说明/提示

数据范围

• $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$
• 输入均为整数

样例解释 1

如果忽略第 $5$ 次操作，则 $x$ 的变化为 $0 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3$，最终 $x$ 的值为 $3$，这是最大值。

由 ChatGPT 4.1 翻译