冬天到了，又到了该毁灭城市的季节了(不是）。HJJ是个喜欢爆破的好孩子，他打算在QAQ城大干一番。
QAQ城是一个环形城市群，它由n个城市组成，编号1到n。只有相邻的城市能够直接互相到达，即第i号城市可以直接到达第i+1号城市和第i-1号城市。特别的，1号和n号城市也可以相互到达（因为是环形城市群嘛）
HJJ每到一个城市都会爆破它，现在HJJ位于1号城并打算爆破所有的n个城市，因此他需要到访每一个城市。 但是QAQ城的警察对他十分不友好（实际上他被通缉了），他如果选择通过相邻城市i与i+1之间的道路，他将花费$c_i$元qwq币去买通路上的警察,$c_n$代表城市n与1之间的费用（每次通过都需要贿赂）。 所以他从领导那儿借来了免费的传送宝珠，使他可以直接传送x个城市 (如果他当前在i号城市，那么它将可以通过传送到达i+x号城市或者i-x,在环的意义上)
HJJ不喜欢警察，所以现在HJJ想知道，他在保证贿赂警察次数最少的情况下最少需要花费多少qwq币才能爆破整个QAQ城
第一行一个整数 $T\ (1\le T\le 10)$ 表示有 $T$ 组输入
接下来 $T$ 组数据
每组数据第一行两个整数 $n$,$x$ $(1\le n\le 10^5,1\le x\le 2\times10^5)$ 分别表示城市群数目，传送宝珠的传送能力。
第二行有 $n$ 个正整数 $c_i$ $(1\le i\le n,1\le c_i\le 2000)$,表示贿赂对应相邻道路的警察的费用。
输出 $T$ 行
每行对应一组输入的答案，输出一个整数表示HJJ最少需要花费的qwq币与最少贿赂次数的乘积。
2 6 3 1 2 3 4 5 6 9 8 2 3 4 5 6 7 8 9 10\n · \n · · · · · \n · \n · · · · · · · · \n
6 0\n \n
第一组数据中环形城市有6个，HJJ每次可以传送3个城市，所以他的路线可以是
1->4->1->2->5->2->3->6
其中只有1->2需要花费1qwq币与2->3需要花费2qwq币，所以一共花费3qwq币，需要贿赂2次，答案为3*2 = 6
第二组数据中HJJ可以不需要贿赂，仅靠传送宝珠就能够到达所有城市并爆破。所以答案为0
Finished