You are given a sequence $a$ of $n$ non-negative integers. You can perform the following two operations any number of times to make all numbers in the sequence equal:

• Pay a cost of $x$ to change $a_i$ to $\max(a_i-1, 0)$ for all positive integers $i \le n$.
• Pay a cost of $y$ to replace any single number in the sequence with any other number.

Find the minimum cost required.

Input

Each test case contains multiple test sets.

The first line contains an integer $t$, representing the number of test cases.

The following lines contain $t$ test cases.

For each test case, the first line contains three positive integers $n, x, y$, representing the sequence length, the cost of the first operation, and the cost of the second operation, respectively. The second line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$ ($1 \le n \le 2 \times 10^5$, $0 \le x, y, a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$.

Output

For each test case, output a single integer representing the minimum cost required.

Examples

Input 1

3
2 4 2
3 10
5 2 1
1 2 2 1 1
5 3 8
0 1 2 3 2

Output 1

2
2
9

Note

For the first test case, you can perform the second operation once to change $a_2$ to $3$, resulting in $a_1=a_2=3$.

For the second test case, you can perform the second operation twice to change $a_2$ and $a_3$ to $1$, resulting in $a_1=a_2=a_3=a_4=a_5=1$.

For the third test case, you can perform the first operation $3$ times, resulting in $a_1=a_2=a_3=a_4=a_5=0$.