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

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.

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.