AT_abc440_c [ABC440C] Striped Horse

> りんごさんは馬を縞模様に塗ってシマウマにしようとしています。 $ 1 $ から $ N $ の番号がついた $ 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 $ 番目のテストケースに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースにおいて、 $ x=4 $ として手順を実行すると、マス $ 1,4,5,8 $ が黒く塗られ、コストの合計は $ 4 $ となります。 コストの合計を $ 4 $ 未満にすることはできないため、これが最小値となります。 ### Constraints - $ 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 $ 以下 - 入力は全て整数