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$。
• 所有输入值均为整数。