分数: 300 点
问题陈述
林檎先生正在尝试给一匹马画上条纹,使其成为斑马。
有 N 编号的方块 1 to N 排成一行。
最初,所有方块都是白色的,绘制方块的成本 i 黑色是 C_i.
考虑执行以下过程一次,将一些方块涂成黑色:
- 选择一个正整数 x 自由。
- 油漆广场 i 所有整数均为黑色 i 满意 1 \leq i \leq N 这样余数当 (i+x) 除以 2W 小于 W.
找出执行此过程的最低总成本。
你被给予 T 测试用例;解决它们中的每一个。
约束
- 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
- 总和 N 超过 T 测试用例最多 2\times 10^5.
- 总和 W 超过 T 测试用例最多 2\times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出,其中 \mathrm{case}_i 表示 i- 第一个测试用例。
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N W C_1 \dots C_N
输出
输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
4 8 2 1 10 10 1 1 10 10 1 8 3 1 10 10 1 1 10 10 1 8 4 1 10 10 1 1 10 10 1 4 100 100000 100000 100000 100000
示例输出 1
4 12 22 0
在第一个测试用例中,如果执行过程 x=4,正方形 1,4,5,8 被漆成黑色,总成本为 4。 总成本不能低于 4,所以这是最小值。