問題文

長さ n の数列 a と正整数 k に対して、以下の条件が成り立つとき、 a を k-連続な数列と定義します。

• すべての i\ (1 \le i \le n) に対して、ある正整数対 (l,r) が存在し、 l\le i < r かつ k \le r-l かつ a_l=a_{l+1}=\ldots=a_{r-1} が成り立つ。

例えば、 a=(1,1,1,2,2,2,2,3,3,3) は 3-連続です。特に、 a=() ならば任意の正整数 t に対して t-連続なことに注意してください。

正整数 N,K と長さ N の正整数列 C,W が与えられます。あなたは、以下の操作を 0 回以上任意の回数行えます。

• 整数 i を選ぶ。コスト W_i を払い、 C_i,W_i をそれぞれ C,W から削除する。

C を K-連続にするために必要なコストの総和の最小値を求めてください。

制約

• 1 \leq K \leq N \leq 2\times 10^5
• 1 \leq C_i \leq N
• 1 \leq W_i \leq 10^9
• 入力は全て整数

部分点

• N \leq 300 を満たすデータセットに正解した場合は、10 点与えられる。
• N \leq 3000 を満たすデータセットに正解した場合は、上記とは別に 10 点与えられる。
• 追加制約のないデータセットに正解した場合は、上記とは別に 80 点与えられる。

入力例 1

4 2
1 1 2 1
1 2 3 4

出力例 1

3

入力例 2

2 1
1 2
10 10

出力例 2

0

入力例 3

10 2
3 1 4 1 5 9 2 6 5 3
58 97 93 23 84 62 64 33 83 27

出力例 3

337