CF1659C.Line Empire

You are an ambitious king who wants to be the Emperor of The Reals. But to do that, you must first become Emperor of The Integers.

Consider a number axis. The capital of your empire is initially at $0$. There are $n$ unconquered kingdoms at positions $0 \lt x_1 \lt x_2 \lt \ldots \lt x_n$. You want to conquer all other kingdoms.

There are two actions available to you:

• You can change the location of your capital (let its current position be $c_1$) to any other conquered kingdom (let its position be $c_2$) at a cost of $a\cdot |c_1-c_2|$.
• From the current capital (let its current position be $c_1$) you can conquer an unconquered kingdom (let its position be $c_2$) at a cost of $b\cdot |c_1-c_2|$. You cannot conquer a kingdom if there is an unconquered kingdom between the target and your capital.

Note that you cannot place the capital at a point without a kingdom. In other words, at any point, your capital can only be at $0$ or one of $x_1,x_2,\ldots,x_n$. Also note that conquering a kingdom does not change the position of your capital.

Find the minimum total cost to conquer all kingdoms. Your capital can be anywhere at the end.

你是一位雄心勃勃的国王，渴望成为“实数帝国”的皇帝。但在此之前，你必须先成为“整数帝国”的皇帝。

考虑一条数轴。你的帝国首都初始位于 $0$。在位置 $0 \lt x_1 \lt x_2 \lt \ldots \lt x_n$ 处有 $n$ 个尚未征服的王国。你希望征服所有这些王国。

你有两种可执行的操作：

• 你可以将首都（设其当前位置为 $c_1$）迁至任意一个已被征服的王国（设其位置为 $c_2$），花费为 $a\cdot |c_1-c_2|$。
• 从当前首都（设其当前位置为 $c_1$）出发，你可以征服一个尚未征服的王国（设其位置为 $c_2$），花费为 $b\cdot |c_1-c_2|$。但若目标王国与首都之间存在至少一个尚未征服的王国，则你无法征服该目标王国。

注意：你不能将首都设在没有王国的位置上。换言之，在任意时刻，你的首都只能位于 $0$ 或 $x_1,x_2,\ldots,x_n$ 中的某一点。另外请注意：征服一个王国不会改变你首都的位置。

求征服所有王国所需的最小总花费。最终你的首都可以位于任意位置。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of each test case follows.

The first line of each test case contains $3$ integers $n$, $a$, and $b$ ($1 \leq n \leq 2 \cdot 10^5$; $1 \leq a,b \leq 10^5$).

The second line of each test case contains $n$ integers $x_1, x_2, \ldots, x_n$ ($1 \leq x_1 \lt x_2 \lt \ldots \lt x_n \leq 10^8$).

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。随后是每个测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$a$ 和 $b$（$1 \leq n \leq 2 \cdot 10^5$；$1 \leq a,b \leq 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$（$1 \leq x_1 \lt x_2 \lt \ldots \lt x_n \leq 10^8$）。

所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, output a single integer — the minimum cost to conquer all kingdoms.

对于每个测试用例，输出一个整数——征服所有王国的最小代价。

Here is an optimal sequence of moves for the second test case:

1. Conquer the kingdom at position $1$ with cost $3\cdot(1-0)=3$.
2. Move the capital to the kingdom at position $1$ with cost $6\cdot(1-0)=6$.
3. Conquer the kingdom at position $5$ with cost $3\cdot(5-1)=12$.
4. Move the capital to the kingdom at position $5$ with cost $6\cdot(5-1)=24$.
5. Conquer the kingdom at position $6$ with cost $3\cdot(6-5)=3$.
6. Conquer the kingdom at position $21$ with cost $3\cdot(21-5)=48$.
7. Conquer the kingdom at position $30$ with cost $3\cdot(30-5)=75$.

The total cost is $3+6+12+24+3+48+75=171$. You cannot get a lower cost than this.

以下是第二个测试用例的最优操作序列：

1. 征服位置 $1$ 处的王国，花费为 $3\cdot(1-0)=3$。
2. 将首都迁至位置 $1$ 处的王国，花费为 $6\cdot(1-0)=6$。
3. 征服位置 $5$ 处的王国，花费为 $3\cdot(5-1)=12$。
4. 将首都迁至位置 $5$ 处的王国，花费为 $6\cdot(5-1)=24$。
5. 征服位置 $6$ 处的王国，花费为 $3\cdot(6-5)=3$。
6. 征服位置 $21$ 处的王国，花费为 $3\cdot(21-5)=48$。
7. 征服位置 $30$ 处的王国，花费为 $3\cdot(30-5)=75$。

总花费为 $3+6+12+24+3+48+75=171$。无法得到比这更低的花费。