인터넷 보급 문제

정부가 긴 고속도로를 따라 늘어선 작은 마을에 인터넷을 보급하려고 한다. 마을은 고속도로를 따라 $N$개가 나란히 붙어 있고, 각 마을은 고속도로를 정확히 1킬로미터씩 차지한다. 마을에는 고속도로를 따라 1번부터 $N$번까지 차례로 번호가 붙어 있다.

인터넷을 연결하려면 위성 회선을 갖춘 접속국을 세워야 한다. 접속국은 서로 다른 마을에 하나씩 세우고, 하나를 세우는 비용은 $B$이다. 정부는 품질을 최대한 높이려고 하기 때문에 모든 집을 접속국 중 하나에 직접 연결한다. $i$번 마을의 집을 $j$번 마을의 접속국에 연결하면 케이블 비용은 $|i - j| \times C$이고, $C$는 케이블 1킬로미터의 가격이다. 마을 안에서 쓰는 케이블 값은 무시할 만큼 작으므로, 접속국이 있는 마을의 집을 그 접속국에 연결하면 케이블 비용은 0이다.

$N$, $B$, $C$와 각 마을의 집 개수가 주어질 때, 모든 마을의 모든 집을 인터넷에 연결하는 최소 비용을 구하는 프로그램을 작성하시오. 비용은 접속국을 세우는 값과 각 집의 케이블 값을 모두 더한 값이다. 접속국을 몇 개 세울지는 아직 정하지 않았으므로, 접속국이 1개, 2개, $\dots$, $N$개일 때의 최소 비용을 각각 구해야 한다.

첫째 줄에 마을의 수 $N$, 접속국 하나를 세우는 비용 $B$, 케이블 1킬로미터의 가격 $C$가 공백으로 구분되어 주어진다 ($1 \le N \le 6000$, $1 \le B \le 10^9$, $1 \le C \le 100$).

둘째 줄에 $N$개의 정수 $H_1, H_2, \dots, H_N$이 공백으로 구분되어 주어진다. $H_i$는 $i$번 마을의 집 개수이다 ($1 \le H_i \le 10^9$).

접속국을 1개, 2개, $\dots$, $N$개 세울 때 모든 집을 연결하는 최소 총비용 $N$개를 공백 하나로 구분해 한 줄에 출력한다.