와이파이 설치

농부 존의 소 $N$마리 ($1 \le N \le 2000$)가 헛간에서 목초지로 이어지는 직선 경로 위 여러 위치에 서 있습니다. 이 경로는 하나의 1차원 수직선으로 생각할 수 있습니다. 소들은 서로 계속 연락하기를 원하므로, 존은 모든 소가 무선 신호를 받을 수 있도록 여러 위치에 와이파이 기지국을 설치하려고 합니다.

기지국의 가격은 신호를 전송할 수 있는 거리(출력)에 따라 달라집니다. 출력이 $r$인 기지국의 가격은 $A + B \cdot r$이며, 여기서 $A$는 기지국 설치의 고정 비용, $B$는 전송 거리 한 단위당 비용입니다. 위치 $x$에 이런 기지국을 설치하면 $x - r$부터 $x + r$까지의 범위에 있는 모든 소에게 신호를 전달할 수 있습니다. 출력이 $r = 0$인 기지국도 설치할 수 있지만, 이 경우 기지국과 정확히 같은 위치에 있는 소에게만 신호를 전달합니다.

$A$와 $B$의 값, 그리고 소들의 위치가 주어질 때, 모든 소에게 무선 신호를 제공하는 가장 저렴한 방법의 비용을 구하세요.

• 첫째 줄: 공백으로 구분된 세 정수 $N$, $A$, $B$ ($0 \le A, B \le 1000$).
• 다음 $N$개의 줄: 각 줄에는 소 한 마리의 위치를 나타내는 $0$ 이상 $1{,}000{,}000$ 이하의 정수가 하나씩 주어집니다.

• 모든 소에게 무선 신호를 제공하는 최소 비용을 출력합니다.
• 답은 항상 $0.5$의 배수입니다. 답이 정수이면 소수점 부분 없이 출력하고, 그렇지 않으면 값 뒤에 .5를 붙여 출력합니다 (예: 57.5).

예를 들어 소 3마리가 위치 $7$, $0$, $100$에 있고, 출력이 $r$인 기지국의 가격이 $20 + 5r$이라고 합시다. 최적해는 위치 $3.5$에 출력 $3.5$인 기지국을 설치해 위치 $0$과 $7$의 소를 신호 범위에 넣고, 위치 $100$에 출력 $0$인 기지국을 하나 더 설치하는 것입니다. 이때 총 비용은 $(20 + 5 \cdot 3.5) + (20 + 5 \cdot 0) = 37.5 + 20 = 57.5$입니다.