\(N\) con bò của Farmer John (\(1 \le N \le 2000\)) đang đứng tại nhiều vị trí khác nhau dọc theo con đường thẳng từ chuồng đến đồng cỏ, có thể xem như một trục số một chiều. Vì những con bò thích giữ liên lạc với nhau qua thư điện tử, FJ muốn lắp đặt các trạm phát Wifi tại nhiều vị trí sao cho tất cả bò đều được phủ sóng không dây.

Sau khi tham khảo giá, FJ biết rằng chi phí của một trạm phát Wifi phụ thuộc vào khoảng cách mà nó có thể truyền tín hiệu: một trạm phát có công suất \(r\) tốn \(A + B \cdot r\), trong đó \(A\) là chi phí cố định để lắp đặt trạm và \(B\) là chi phí trên mỗi đơn vị khoảng cách truyền tín hiệu. Nếu FJ lắp một thiết bị như vậy tại vị trí \(x\), nó có thể truyền dữ liệu đến mọi con bò nằm trong khoảng từ \(x-r\) đến \(x+r\). Trạm phát có công suất truyền \(r=0\) vẫn được phép, nhưng khi đó nó chỉ phủ sóng cho một con bò ở đúng vị trí của trạm phát.

Cho các giá trị \(A\), \(B\) và vị trí của những con bò, hãy xác định phương án ít tốn kém nhất để FJ phủ sóng không dây cho tất cả bò.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(N\), \(A\) và \(B\), cách nhau bởi dấu cách (\(0 \le A, B \le 1000\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên trong khoảng từ \(0\) đến \(1\,000\,000\), mô tả vị trí của một con bò của FJ.

Dữ liệu ra

In ra chi phí nhỏ nhất để phủ sóng không dây cho tất cả bò.

Ví dụ

3 20 5
7
0
100

57.5

Nguồn

USACO 2012 December Contest, Silver — Problem 2: Wifi Setup

Tác giả đề: Brian Dean, 2012.