AT_abc440_c [ABC440C] Striped Horse

> Ringo-san is trying to paint a horse with stripes to make it a zebra. There are $ N $ squares numbered $ 1 $ to $ N $ arranged in a line. Initially, all squares are white, and the cost of painting square $ i $ black is $ C_i $ . Consider performing the following procedure once to paint some squares black: - Choose a positive integer $ x $ freely. - Paint square $ i $ black for all integers $ i $ satisfying $ 1 \leq i \leq N $ such that the remainder when $ (i+x) $ is divided by $ 2W $ is less than $ W $ . Find the minimum total cost to perform this procedure. You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format, where $ \mathrm{case}_i $ denotes the $ i $ -th test case. > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $ $ W $ $ C_1 $ $ \dots $ $ C_N $

Output $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 In the first test case, if the procedure is executed with $ x=4 $ , squares $ 1,4,5,8 $ are painted black, and the total cost is $ 4 $ . The total cost cannot be less than $ 4 $ , so this is the minimum. ### 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 $ - The sum of $ N $ over the $ T $ test cases is at most $ 2\times 10^5 $ . - The sum of $ W $ over the $ T $ test cases is at most $ 2\times 10^5 $ . - All input values are integers.