E2. Make Them Equivalent
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, and a positive integer $$$k \lt n$$$, and a positive integer $$$x$$$.

You can perform any one of two operations several times (possibly zero):

  • Choose an integer $$$i$$$ where $$$1 \le i \le n$$$, and decrement $$$a_i$$$ (that is, perform the assignment $$$a_i := a_i - 1$$$). This operation costs $$$x$$$.
  • Choose an integer $$$i$$$ where $$$1 \le i \le n$$$, and increment $$$a_i$$$ (that is, perform the assignment $$$a_i := a_i + 1$$$). This operation costs $$$x$$$.

Find the minimum cost to achieve $$$a_i = a_{i + k}$$$ for all $$$i$$$ such that $$$1 \le i \le n - k$$$.

Input

The first line of input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$), the number of test cases.

The first line of each test case contains three integers $$$n, k, x$$$ ($$$1 \le k \lt n \le 10^5$$$, $$$1 \le x \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le 10^4$$$).

The sum of $$$n$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$.

Output

For each test case, output one line containing one integer, the minimum cost to achieve $$$a_i = a_{i + k}$$$ for all $$$i$$$ such that $$$1 \le i \le n - k$$$.

Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

Example
Input
3
8 2 4
1 3 5 7 9 11 13 15
6 3 10
1 1 1 2 2 2
5 1 1
1 2 3 9 100
Output
128
30
106
Note

In the first test case, you can:

  • Increment the first four values of the array by the following values $$$6, 6, 2, 2$$$ (that is, for example, increment the first element $$$6$$$ times), making the array in the form $$$7, 9, 7, 9, 9, 11, 13, 15$$$.
  • Decrement the last four values of the array by the following values $$$2, 2, 6, 6$$$ (that is, for example, decrement the last element $$$6$$$ times), making the array in the form $$$7, 9, 7, 9, 7, 9, 7, 9$$$, which satisfies the requirement with $$$k = 2$$$.

This will cost $$$(6 + 6 + 2 + 2 + 2 + 2 + 6 + 6) \cdot 4 = 128$$$.