Phủ sóng Wifi

Có $N$ con bò đứng tại các vị trí phân biệt trên trục số. Cần đặt các trạm wifi để phủ sóng tất cả các bò. Một trạm có bán kính $r$ đặt tại $x$ phủ sóng mọi điểm trong $[x-r,x+r]$, chi phí là $A+B·r$ (với $r\ge 0$).

Tìm chi phí nhỏ nhất để phủ sóng tất cả các bò.

Dữ liệu vào

• Dòng $1$: Ba số nguyên $N$, $A$, $B$ ($1\le N\le 2000$, $0\le A,B\le 1000$).
• $N$ dòng tiếp: Vị trí mỗi con bò (số nguyên trong $[0,{10}^6]$).

Dữ liệu ra

Chi phí nhỏ nhất (có thể là số thực, in chính xác).

Ràng buộc

• $1\le N\le 2000$
• $0\le A,B\le 1000$
• Vị trí bò trong $[0,{10}^6]$

Ví dụ