Problem Description

Takahashi's winter vacation lasts for $ N $ days. Takahashi is planning his meals for these $ N $ days.

On the $ i $-th day, if $ T_i $ is $ 0 $, he plans to go to a ramen shop, and if $ T_i $ is $ 1 $, he plans to go to a restaurant. The deliciousness of the meal is $ A_i $.

Takahashi has a gourmet level, which initially is $ 0 $. When Takahashi eats at a ramen shop, his gourmet level decreases by $ 1 $. When Takahashi eats at a restaurant, his gourmet level increases by $ 1 $.

Takahashi wants to keep his gourmet level between $ 0 $ and $ K $ inclusive. Takahashi can cancel zero or more meal plans and cook for himself. If he cooks, his gourmet level does not change, and the deliciousness of the meal is $ 0 $.

Find the maximum total deliciousness Takahashi can achieve during his winter vacation.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ T_1 $ $ A_1 $ $ : $ $ T_{N} $ $ A_{N} $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

8 2
1 3
1 7
0 2
1 8
1 4
0 6
0 2
0 4

Sample Output #1

31

Sample Input #2

15 3
0 3
1 4
1 5
0 2
0 9
0 11
1 6
1 2
1 6
0 4
1 7
0 4
1 8
1 4
1 9

Sample Output #2

73

Sample Input #3

5 3
1 1000000000
0 1000000000
1 1000000000
0 1000000000
1 1000000000

Sample Output #3

5000000000

Notes/Hints

Constraints

• $1 \leq K \leq N \leq 10^{5}$
• $1 \leq A_i \leq 10^9$
• $ T_i $ is either 0 or 1
• All given inputs are integers

Sample Explanation 1

• Day 1: Cook for himself. Gourmet level remains $ 0 $
• Day 2: Go to a restaurant. Gourmet level becomes $ 1 $
• Day 3: Go to a ramen shop. Gourmet level becomes $ 0 $
• Day 4: Go to a restaurant. Gourmet level becomes $ 1 $
• Day 5: Go to a restaurant. Gourmet level becomes $ 2 $
• Day 6: Go to a ramen shop. Gourmet level becomes $ 1 $
• Day 7: Cook for himself. Gourmet level remains $ 1 $
• Day 8: Go to a ramen shop. Gourmet level becomes $ 0 $
• The total deliciousness of the meals is $ 7 + 2 + 8 + 4 + 6 + 4 = 31 $, which is the maximum.

Sample Explanation 3

• Note that the answer can be very large.

见题面 Input 部分

见题面 Output 部分