The city of Otnorot is considering battling congestion on its subway lines by adding relief tunnels along each line. A relief tunnel is an additional tunnel that runs along a subsegment of the line which allows extra trains to operate in that subsegment.

Each segment between two consecutive stops of a subway line requires some minimum amount of relief lines to operate without congestion. The cost to build a relief tunnel is a fixed start up cost ~S~ and an additional rate ~R~ for each segment the relief tunnel services.

Given the number of additional relief tunnels required for each segment, what is the minimum cost required to meet the requirements?

Input Specification

The input contains 10 datasets. Each dataset begins with three terms ~N~, ~R~, ~S~ ~(1 \le N, R, S \le 1\,000\,000)~, the number of segments on the subway line, the rate per segment, and the fixed cost. The next line contains ~N~ integers ~A_i~ ~(0 \le A_i \le 1\,000\,000)~, the number of additional relief tunnels required in the ~i~-th segment.

For the first 3 cases, ~A_i \le 1~.
For the first 6 cases, ~N \le 1\,000~.

Output Specification

For each dataset, output the minimum cost required to meet the relief tunnel requirements.

Sample Input (Two Datasets Shown)

4 1 2
2 1 1 2
5 1 10
2 1 1 1 2

Sample Output

12
30

Explanation of Sample Datasets

In the first dataset, it's best to have one tunnel run the length of the line, one tunnel only service the first segment, and one tunnel only service the last segment. This has a total cost of ~(2+4) + (2+1) + (2+1) = 12~.
In the second dataset, it's best to have two tunnels run the length of the line due to the high start up cost. This has a total cost of ~(10+5) + (10+5) = 30~.

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org