AT_agc071_d [AGC071D] Level K Terms

整数 $ N,K $ および長さ $ N $ の非負整数列 $ A=(A_1,A_2,\dots,A_N) $ が与えられます。 $ A $ は単調非減少列です。すなわち、 $ i=1,2,\dots,N-1 $ に対して $ A_i \leq A_{i+1} $ が成り立ちます。 長さ $ N $ の単調非減少列である非負整数列 $ X=(X_1,X_2,\dots,X_N) $ に対して以下の操作を $ 0 $ 回以上行うことで $ X $ の全ての項の値を $ 0 $ にできるとき、 $ X $ は「良い数列」であるといいます。 - $ 1 \leq i \leq N-K+1 $ を満たす整数 $ i $ を選ぶ。 $ S=X_i+X_{i+1}+\dots +X_{i+K-1} $ とする。 $ X $ の $ i,i+1,\dots,i+K-1 $ 項目の値を全て $ \left\lfloor \frac{S}{K}\right\rfloor $ で置き換える。 以下の条件をすべて満たす非負整数列 $ B=(B_1,B_2,\dots,B_N) $ に対する $ \sum_{i=1}^N B_i $ の最大値を求めてください。 - $ i=1,2,\dots,N $ に対し、 $ B_i \leq A_i $ が成り立つ。 - 非負整数列 $ B $ は単調非減少列であり、「良い数列」である。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ 各ケースは以下の形式で与えられる。 > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

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

### Sample Explanation 1 $ 1 $ 番目のテストケースについて、 $ A $ は「良い数列」になっています。これについて、例えば操作を以下の手順で行うことで $ A $ の全ての項の値を $ 0 $ にできます。 1. $ i=3 $ とする。 $ S=A_3+A_4=5 $ となり、 $ A $ の $ 3,4 $ 項目の値は $ \left\lfloor \frac{5}{2}\right \rfloor = 2 $ に置き換えられ、 $ A=(0,1,2,2) $ となる。 2. $ i=2 $ とする。 $ S=A_2+A_3=3 $ となり、 $ A $ の $ 2,3 $ 項目の値は $ \left\lfloor \frac{3}{2}\right \rfloor = 1 $ に置き換えられ、 $ A=(0,1,1,2) $ となる。 3. $ i=3 $ とする。 $ S=A_3+A_4=3 $ となり、 $ A $ の $ 3,4 $ 項目の値は $ \left\lfloor \frac{3}{2}\right \rfloor = 1 $ に置き換えられ、 $ A=(0,1,1,1) $ となる。 4. $ i=1 $ とする。 $ S=A_1+A_2=1 $ となり、 $ A $ の $ 1,2 $ 項目の値は $ \left\lfloor \frac{1}{2}\right \rfloor = 0 $ に置き換えられ、 $ A=(0,0,1,1) $ となる。 5. $ i=2 $ とする。 $ S=A_2+A_3=1 $ となり、 $ A $ の $ 2,3 $ 項目の値は $ \left\lfloor \frac{1}{2}\right \rfloor = 0 $ に置き換えられ、 $ A=(0,0,0,1) $ となる。 6. $ i=3 $ とする。 $ S=A_3+A_4=1 $ となり、 $ A $ の $ 3,4 $ 項目の値は $ \left\lfloor \frac{1}{2}\right \rfloor = 0 $ に置き換えられ、 $ A=(0,0,0,0) $ となる。 よって $ B=A $ とすることで最大値 $ 0+1+2+3=6 $ を達成します。 $ 2 $ 番目のテストケースについて、 $ A $ は「良い数列」ではありません。 $ B=(0,0,2,3) $ とすると $ B $ は「良い数列」であり、条件を満たします。 ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 2 \leq K \leq N \leq 2 \times 10^5 $ - $ 0\leq A_i \leq 10^{9} $ - $ i=1,2,\dots,N-1 $ に対して $ A_i \leq A_{i+1} $ が成り立つ - 入力される値はすべて整数 - $ 1 $ つの入力に含まれるテストケースについて、 $ N $ の総和は $ 2 \times 10^5 $ 以下