Problem6660--ABC249 — F - Ignore Operations

6660: ABC249 — F - Ignore Operations

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 1Submit Num: 1StatisticsShowOff!

Description

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$.

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.

Constraints

$1≤N≤2×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.

Sample 1 Input 

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

Sample 1 Output 

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 2 Input 

1 0
2 -1000000000

Sample 2 Output 

-1000000000

Sample 3 Input 

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

Sample 3 Output 

15

Source/Category

AtCoder_ABC 100.249.ABC249 
Submit