← 返回题目列表

AtCoder · abc440_c

E. 条纹马

中文机器翻译题面 查看原题

分数: 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,所以这是最小值。