F - Ignore Operations Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

高橋君は整数 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 の値としてあり得る最大値を求めてください。

制約

  • 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

Score : 500 points

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