Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

I. Дракон доставляет
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Я стоял прямо перед огромным замком из чёрного камня, по стенам которого стекали струи дождевой воды. Издалека виднелась высокая башня, в самом верхнем помещении которой горел свет. Я чувствовал, что Дракон там. Он всегда любил быть выше других. Где-то там внутри была и алхимическая лаборатория по производству Синего Чая. Там его расфасовывали и доставляли заказчикам по всему городу, как пиццу или гамбургеры.

Заказы приходили голубиной почтой в моменты времени ti. Одна мгновенная доставка Чая обходилась Дракону в d золотых, но она могла объединять любое количество пришедших ранее заказов. Задержка каждого заказа обходилась в c золотых за единицу времени. Система была отлажена и работала как часы, так чтобы минимизировать суммарные затраты на доставки, а рыцари послушно закрывали на неё глаза. Золото всегда негативно влияло на зрение людей.

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

В первой строке записаны три целых числа через пробел: n, d и c (1 ≤ n ≤ 103, 1 ≤ d ≤ 109, 1 ≤ c ≤ 106) — количество заказов, стоимость одной доставки, а также стоимость единицы времени задержки одного заказа соответственно.

Во второй строке записаны n целых чисел через пробел: ti (0 ≤ ti ≤ 109) — моменты времени, в которые поступают заказы. Гарантируется, что последовательность моментов времени возрастает, то есть ti < ti + 1.

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

Выведите единственное целое число — минимальную суммарную стоимость всех доставок.

Примеры
Входные данные
3 3 2
2 5 7
Выходные данные
9
Входные данные
3 3 1
2 5 6
Выходные данные
7
Примечание

В первом примере выгоднее доставить все три заказа в момент их прихода, а во втором — доставить второй заказ вместе с третьим.