AT_abc456_f [ABC456F] Plan Holidays

高橋君は $ N $ 日間のスケジュールを決めようとしています。初期状態ではどの日も休日ではありません。 以下のいずれかの操作を好きな回数繰り返すことができます。 - $ 1 $ 以上 $ N $ 以下の整数 $ i $ を選び、 $ i $ 日目を休日にする。この操作にはコストが $ A_i $ かかる。 - $ 2 $ 以上 $ N-1 $ 以下の整数 $ i $ のうち $ i-1 $ 日目と $ i+1 $ 日目がすでにどちらも休日であるような $ i $ を選び、 $ i $ 日目を休日にする。この操作にはコストはかからない。 連続する $ K $ 日以上の休日を作るために必要なコストの総和の最小値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ ここで $ \mathrm{case}_i $ は $ i $ 番目のテストケースの入力を意味する。各テストケースは以下の形式で与えられる。 > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースについての答えを出力せよ。

### Sample Explanation 1 一つ目のテストケースについて、以下のように操作すると $ 2 $ 日以上連続する休日を作ることができます。 - $ 2 $ 日目を一種類目の操作で休日にする。コストが $ 1 $ かかる。 - $ 4 $ 日目を一種類目の操作で休日にする。コストが $ 1 $ かかる。 - $ 3 $ 日目を二種類目の操作で休日にする。コストはかからない。 この操作方法のコストの総和は $ 2 $ です。コスト $ 2 $ 未満で $ 2 $ 日以上連続する休日を作ることはできないため、 $ 2 $ を出力してください。 ### Constraints - $ 1 \leq T \leq 2 \times 10^5 $ - $ 1 \leq K \leq N \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq 10^9 $ - 入力はすべて整数 - 全てのテストケースにおける $ N $ の総和は $ 2\times 10^5 $ 以下