Problem J
Jackdaws And Crows

A Clattering of Jackdaws by Dun.can on flickr, cc by

A comment chain is alternating if the scores $s_1,s_2,\dots ,s_n$ of the comments all are non-zero, and every pair of adjacent scores $s_i$, $s_{i+1}$ have opposite signs. In particular, a single comment with a non-zero score or even a comment chain without any comment is an alternating comment chain.

There are two operations Nick can do to make the comment chain alternating:

1. Create a fake account and upvote/downvote some of the comments. This increases/decreases their respective scores by $1$. Each fake account can only upvote/downvote each comment at most once, but it can vote on any subset of the comments. It takes $c$ seconds to create an account and use it to vote (regardless of how many comments are upvoted/downvoted).

2. Report one specific comment to remove it from the chain. Thinking of convincing reasons for the report takes $r$ seconds. (Nick is an excellent arguer, so once the report is filed, the comment is guaranteed to be removed.)

Nick can apply these operations in any order, any number of times. How fast can he make the comment chain alternating?

For example, consider Sample Input 1 below, where the scores in the comment chain are $8,8,2,-2$, and it takes Nick $10$ seconds to create an account and $50$ seconds to file a report for one comment. In this case it is optimal to first create $3$ fake accounts and use them to upvote the fourth comment and downvote the third, followed by reporting the first comment. This results in the scores $8,-1,1$, which is an alternating chain. The time used for this is $80$ seconds.

Input

The input consists of:

• One line with three integers $n$, $c$, and $r$ ($1\le n\le 5\cdot {10}^5$, $1\le c,r\le {10}^9$), the number of comments in the chain, the time it takes to create a fake account and the time it takes to report one comment respectively.

• One line with $n$ integers $s_1,\dots ,s_n$ ($-{10}^9\le s_i\le {10}^9$ for all $i$), the current score of each comment in the chain.

Output

Output the smallest time to make the comment chain alternating by applying the operations above.

4 10 50
8 8 2 -2

80

6 100 33
5 -13 0 0 -12 0

132