C. Империя на прямой
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы — амбициозный король, который хочет быть Императором Действительных чисел. Но перед этим вам нужно стать Императором Целых чисел.

Рассмотрим числовую ось. Столица вашей империи изначально находится в точке $$$0$$$. На прямой есть $$$n$$$ незахваченных королевств в позициях $$$0<x_1<x_2<\ldots<x_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$$$. Также обратите внимание, что захват королевства не изменяет положение вашей столицы.

Выведите минимальную суммарную стоимость захвата всех королевств. Ваша столица может оказаться в итоге в любой точке.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следуют описания наборов.

Первая строка каждого набора содержит $$$3$$$ целых числа $$$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 < x_2 < \ldots < x_n \leq 10^8$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно число: минимальную стоимость захвата всех королевств.

Пример
Входные данные
4
5 2 7
3 5 12 13 21
5 6 3
1 5 6 21 30
2 9 3
10 15
11 27182 31415
16 18 33 98 874 989 4848 20458 34365 38117 72030
Выходные данные
173
171
75
3298918744
Примечание

Ниже приведена оптимальная последовательность действий для второго примера:

  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$$$. Нельзя получить меньшую стоимость.