Nick 是一位观鸟爱好者，经常访问“CrowFinders”论坛与志同道合的人讨论他的爱好。CrowFinders 有一个投票系统，用户可以对评论进行点赞或点踩，这会使评论的分数增加或减少 1。这意味着每条评论最终的分数可以是任何整数（包括负数）。有一次，当 Nick 在浏览关于将寒鸦归类为乌鸦的激烈讨论时，他发现了一些令人愉悦的事情：一串评论的分数在正数和负数之间交替。但几天后，他发现评论链不再交替了。现在 Nick 想让它再次交替。

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

如果评论链的分数 $s_1, s_2, \dots, s_n$ 均不为零，且每一对相邻的分数 $s_i, s_{i+1}$ 符号相反，则称该评论链是交替的。特别地，单条非零分数的评论，甚至没有评论的评论链，都是交替评论链。

Nick 可以执行以下两种操作来使评论链变得交替：

1. 创建一个虚假账号并对部分评论进行点赞/点踩。这会使它们各自的分数增加/减少 1。每个虚假账号对每条评论最多只能点赞/点踩一次，但它可以对评论的任意子集进行投票。创建一个账号并使用它进行投票需要 $c$ 秒（无论点赞/点踩了多少条评论）。
2. 举报一条特定的评论以将其从链中移除。构思举报理由需要 $r$ 秒。（Nick 是一位出色的辩论者，所以一旦提交举报，该评论保证会被移除。）

Nick 可以按任意顺序、任意次数执行这些操作。他最快需要多少时间才能使评论链变得交替？

例如，考虑下方的样例 1，评论链的分数是 $8, 8, 2, -2$，Nick 创建一个账号需要 10 秒，举报一条评论需要 50 秒。在这种情况下，最优方案是先创建 3 个虚假账号，用它们给第四条评论点赞并给第三条评论点踩，然后举报第一条评论。这使得分数变为 $8, -1, 1$，这是一个交替链。所用的总时间为 80 秒。

输入格式

输入包含：

• 第一行包含三个整数 $n, c$ 和 $r$ ($1 \le n \le 5 \cdot 10^5, 1 \le c, r \le 10^9$)，分别表示评论链中的评论数量、创建一个虚假账号所需的时间以及举报一条评论所需的时间。
• 第二行包含 $n$ 个整数 $s_1, \dots, s_n$ ($-10^9 \le s_i \le 10^9$，对于所有 $i$)，表示链中每条评论的当前分数。

输出格式

输出通过应用上述操作使评论链变得交替所需的最短时间。

样例

输入格式 1

4 10 50
8 8 2 -2

输出格式 1

80

输入格式 2

6 100 33
5 -13 0 0 -12 0

输出格式 2

132