102495: [AtCoder]ABC249 F - Ignore Operations

Problem Statement

Takahashi has an integer $x$. Initially, $x = 0$.

There are $N$ operations. The $i$-th operation $(1 \leq i \leq N)$ is represented by two integers $t_i$ and $y_i$ as follows:

• If $t_i = 1$, replace $x$ with $y_i$.
• If $t_i = 2$, replace $x$ with $x + y_i$.

Takahashi may skip any number between $0$ and $K$ (inclusive) of the operations. When he performs the remaining operations once each without changing the order, find the maximum possible final value of $x$.

Constraints

• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

3

If he skips the $5$-th operation, $x$ changes as $0 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3$, so $x$ results in $3$. This is the maximum.

Sample Input 2

1 0
2 -1000000000

Sample Output 2

-1000000000

Sample Input 3

10 3
2 3
2 -1
1 4
2 -1
2 5
2 -9
2 2
1 -6
2 5
2 -3

Sample Output 3

15

题目描述

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