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$ 个测试用例的答案。

约束条件

• $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}$
• 输入中的所有值均为整数
• 单个输入文件中所有测试用例的 $N$ 总和不超过 $2 \times 10^5$

样例解释 #1

对于第一个测试用例，$A$ 本身是「好序列」。例如，通过以下步骤可将所有项变为 $0$：

1. 选择 $i=3$，计算 $S = A_3 + A_4 = 5$，将第 $3, 4$ 项替换为 $\left\lfloor \frac{5}{2} \right\rfloor = 2$，得到 $A = (0, 1, 2, 2)$。
2. 选择 $i=2$，计算 $S = A_2 + A_3 = 3$，将第 $2, 3$ 项替换为 $\left\lfloor \frac{3}{2} \right\rfloor = 1$，得到 $A = (0, 1, 1, 2)$。
3. 选择 $i=3$，计算 $S = A_3 + A_4 = 3$，将第 $3, 4$ 项替换为 $\left\lfloor \frac{3}{2} \right\rfloor = 1$，得到 $A = (0, 1, 1, 1)$。
4. 选择 $i=1$，计算 $S = A_1 + A_2 = 1$，将第 $1, 2$ 项替换为 $\left\lfloor \frac{1}{2} \right\rfloor = 0$，得到 $A = (0, 0, 1, 1)$。
5. 选择 $i=2$，计算 $S = A_2 + A_3 = 1$，将第 $2, 3$ 项替换为 $\left\lfloor \frac{1}{2} \right\rfloor = 0$，得到 $A = (0, 0, 0, 1)$。
6. 选择 $i=3$，计算 $S = A_3 + A_4 = 1$，将第 $3, 4$ 项替换为 $\left\lfloor \frac{1}{2} \right\rfloor = 0$，得到 $A = (0, 0, 0, 0)$。
   因此，取 $B = A$ 可得到最大值 $0 + 1 + 2 + 3 = 6$。

对于第二个测试用例，$A$ 不是「好序列」。取 $B = (0, 0, 2, 3)$ 时 $B$ 是「好序列」且满足条件。

翻译由 DeepSeek R1 完成