|Codeforces Round 782 (Div. 2)|
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<x_1<x_2<\ldots<x_n$$$. You want to conquer all other kingdoms.
There are two actions available to you:
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.
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 < x_2 < \ldots < x_n \leq 10^8$$$).
The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output a single integer — the minimum cost to conquer all kingdoms.
45 2 73 5 12 13 215 6 31 5 6 21 302 9 310 1511 27182 3141516 18 33 98 874 989 4848 20458 34365 38117 72030
173 171 75 3298918744
Here is an optimal sequence of moves for the second test case:
The total cost is $$$3+6+12+24+3+48+75=171$$$. You cannot get a lower cost than this.