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.

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

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

见题面 Input 部分

见题面 Output 部分