N (1 <= N <= 2000) коров Фермера Джона расположены на прямой линии (дороге от амбара до пастбища). ФД хочет расставить вдоль этой прямой точки беспроводного доступа в Internet, так чтобы все коровы были в зоне покрытия.
Стоимость wifi-станции зависит от расстояния, ан которое она может передавать сигнал. Станция с мощностью(радиусом действия) r стоит A + B*r , где A - фиксированная цена установки станции B - стоимость на 1 расстояния, на которое передается информация.
Если такая станция установлена в позиции x, то она может передавать данные до любой коровы, расположенной в интевале x-r...x+r. Допускается станция с мощностью передачи 0, но, поскольку r=0, она будет работать только для коровы, размещенной в самой точке x размещения станции.
По заданным величинам A и B, а также координатам коров, определите самый дешевый способ, которым ФД сможет обеспечить беспроводное покрытие всех своих коров.
PROBLEM NAME: wifi
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа: N A B (0 <= A, B <= 1000).
* Строки 2..1+N: Каждая строка содержит одно целое число в диапазоне 0..1,000,000 описывающее размещение одной коровы.
Формат выходных данных
* Строка 1: Минимальная стоимость обеспечения беспроводным покрытием всех коров.
Примечание
Оптимальное решение - построить базовую станцию в позиции 3.5 (с мощностью/радиусом действия 3.5) и другую станции в позиции 100 с мощностью (радиусом действия) 0. Первая станция обеспечит покрытие коров 1 и 2, вторая - коровы 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 20 5
7
0
100
|
57.5
|