Given an array A of n elements.

You have to make the array A "good" in minimum cost.

The array A is good, if all the pairs of elements {A_i, A_j}  (1 < i, j < n, i != j ) have their pair product equal to the square of maximum element in array A.

There are two different operations by which elements in array A can be converted into other elements:

• An element A_i of array A can be converted into other element  (of any other value)  in cost x.
• A group of exactly k elements of array A can be converted to exactly k elements (of any other value) in cost y. 

You can apply atmost one operation on each element.

Find the minimum cost to make array A "good".

Input

The first line contains an integer t (1 ≤ t ≤ 10³) — the number of test cases in the input. Then t test cases follow.

The first line contains four positive integers n, x, k, y (2 < n < 10⁴) ,(1 ≤ x,y ≤ 10⁵) , (2< k< n) — length of the array, cost of first operation, number of elements in a group in second operation and cost of second operation, respectively.

The second line contains n positive integers A₁, A₂,…, A_n ( 0 ≤ A_i ≤ 10⁵ ), where A_i is the i-th element of the array A.

The sum of n in all testcases does not exceed 10⁷.

Output

Print a single integer in new line - the minimum cost to make array good.