Вы — амбициозный король, который хочет быть Императором Действительных чисел. Но перед этим вам нужно стать Императором Целых чисел.
Рассмотрим числовую ось. Столица вашей империи изначально находится в точке \(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\). Также обратите внимание, что захват королевства не изменяет положение вашей столицы.
Выведите минимальную суммарную стоимость захвата всех королевств. Ваша столица может оказаться в итоге в любой точке.
Выходные данные
Для каждого набора входных данных выведите одно число: минимальную стоимость захвата всех королевств.
Примечание
Ниже приведена оптимальная последовательность действий для второго примера:
- Захватить королевство в точке \(1\), стоимость \(3\cdot(1-0)=3\).
- Переместить столицу в королевство в точке \(1\), стоимость \(6\cdot(1-0)=6\).
- Захватить королевство в точке \(5\), стоимость \(3\cdot(5-1)=12\).
- Переместить столицу в королевство в точке \(5\), стоимость \(6\cdot(5-1)=24\).
- Захватить королевство в точке \(6\), стоимость \(3\cdot(6-5)=3\).
- Захватить королевство в точке \(21\), стоимость \(3\cdot(21-5)=48\).
- Захватить королевство в точке \(30\), стоимость \(3\cdot(30-5)=75\).
Суммарная стоимость \(3+6+12+24+3+48+75=171\). Нельзя получить меньшую стоимость.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|