問題文

高橋君の冬休みは $N$ 日あります。 高橋君は $N$ 日間の食事の予定を考えています。

$i$ 日目の予定は $T_i$ が $0$ ならばラーメン屋に行く予定であり、 $T_i$ が $1$ ならばレストランに行く予定です。食事の美味しさは $A_i$ です。

高橋君には グルメ度 があり、はじめグルメ度は $0$ です。 高橋君がラーメン屋でご飯を食べた場合、グルメ度は $1$ 減少 します。 高橋君がレストランでご飯を食べた場合、グルメ度は $1$ 増加 します。

高橋君はグルメ度を $0$ 以上 $K$ 以下に保ちたいです。 高橋君は $0$ 個以上の食事の予定をキャンセルし、自炊をすることができます。自炊をした場合、グルメ度は変化せず、食事の美味しさは $0$ です。

高橋君が冬休みで得られる美味しさの総和の最大値を求めてください。

制約

• $1 \\leq K \\leq N \\leq 10^{5}$
• $1 \\leq A_i \\leq 10^9$
• $T_i$ は 0 あるいは 1
• 与えられる入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

答えを出力せよ。

入力例 1

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

出力例 1

31

• $1$ 日目：自炊をする。グルメ度は $0$ のままです
• $2$ 日目：レストランに行く。グルメ度は $1$ になります
• $3$ 日目：ラーメン屋に行く。グルメ度は $0$ になります
• $4$ 日目：レストランに行く。グルメ度は $1$ になります
• $5$ 日目：レストランに行く。グルメ度は $2$ になります
• $6$ 日目：ラーメン屋に行く。グルメ度は $1$ になります
• $7$ 日目：自炊をする。グルメ度は $1$ のままです
• $8$ 日目：ラーメン屋に行く。グルメ度は $0$ になります
• 得られる食事の美味しさの総和は $7+2+8+4+6+4 = 31$ となり、これが最大です。

入力例 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

出力例 2

73

入力例 3

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

出力例 3

5000000000

• 答えが大きくなりうることに注意してください