Путешествие с запада на восток
Путешествие с запада на восток
Есть n городов, стоящих на прямой с запада на восток. Города пронумерованы от 1 до n, в порядке с запада на восток. Каждая точка на прямой имеет свою одномерную координату, и точка ближе к востоку имеет большую координату. Координата i-го города - xi
.
Сейчас Вы находитесь в 1 городе, и хотите посетить все города. У вас есть два способа путешествовать:
- Ходить по прямой. При этом ваш уровень усталости будет увеличиваться на a единиц каждый раз, когда Вы будете перемещаться на расстояние 1, независимо от направления.
- Телепортироваться в любую точку, которую хотите. Ваш уровень усталости будет увеличиваться на b единиц, независимо от телепортированного расстояния.
Входные данные
Первая строка содержит три числа n (2 ≤ n ≤ 105
), a и b (1 ≤ a, b ≤ 109
). Следующая строка содержит n целых чисел x1
, x2
, ... , xn
(1 ≤ xi
≤ 109
). Для всех i (1 ≤ i ≤ n – 1) имеет место неравенство xi
< xi+1
.
Выходные данные
Выведите минимально возможный уровень усталости, при котором вы посетите все города.
Объяснение
Тест 1.
Из 1 города ходим во 2-ой, после телепортируемся в 3-ий. В конце ходим в 4-ый. Уровень усталости в конце будет равен 2 * 1 + 5 + 2 * 2 = 11, что является минимально возможным.
Тест 3.
Посещайте все города, в любом порядке, телепортируясь шесть раз. Уровень усталости будет равен 12, что является минимально возможным.
4 2 5 1 2 5 7
11
6 3 7 1 3 6 10 11 13
29
7 1 2 24 35 40 68 72 99 103
12