F - Ignore Operations /

問題文

N 個の操作があります。i \, (1 \leq i \leq N) 個目の操作は整数 t_i, y_i を用いて以下のように表されます。

• t_i = 1 のとき、xy_i で置き換える。
• t_i = 2 のとき、xx + y_i で置き換える。

制約

• 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 個目の操作を無視すると、x0 \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


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