AT_abc440_c [ABC440C] Striped Horse

#### 问题陈述 > 林格先生想给一匹马画上斑马纹。 有 $N$ 个方格，编号为 $1$ 至 $N$ 排列成一行。 初始时，所有方格都是白色的，将方格 $i$ 涂成黑色的成本是 $C_i$ 。 考虑执行下面的程序一次，将一些方格涂成黑色： - 自由选择一个正整数 $x$ 。 - 对于所有满足 $1 \leq i \leq N$ 的整数 $i$，若 $(i + x)$ 除以 $2W$ 后的余数小于 $W$，则将正方形 $i$ 涂成黑色。 求执行此程序的最小总成本。 给你 $T$ 个测试用例，请逐个求解。

输入内容由标准输入法提供，格式如下，其中 $\mathrm{case}_i$ 表示第 $i$ 个测试用例。 >$T\\$ $\mathrm{case}_1\\$ $\vdots\\$ $\mathrm{case}_T$ 每个测试用例的格式如下： >$N$ $W\\$ $C_1$ $\dots$ $C_N$

输出 $T$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。

#### 样列解释 #1 在第一个测试案例中，如果以 $x=4$ 执行程序，则 $1,4,5,8$ 个方格被涂成黑色，总成本为 $4$ 。总成本不可能小于 $4$ ，因此这是最小值。 #### 数据范围 - $1\leq T \leq 2\times 10^5$ - $1\leq N \leq 2\times 10^5$ - $1\leq W \leq 2\times 10^5$ - $1\leq C_i \leq 10^9$ - $T$ 个测试用例中 $N$ 的总和最多为 $2\times 10^5$。 - $T$ 个测试用例中 $W$ 的总和最多为 $2\times 10^5$。 - 所有输入值均为整数。