M. 魔法使考核
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

见习魔法少女 Chiaro 正在参加魔法使考试，大魔法使 Shiro 在她面前放置了 $$$n$$$ 个没有任何魔力值的魔法球，Chiaro 需要施加若干次魔法，让这些魔力球各装满指定大小的魔力值。

具体来说，初始时这些魔法球的魔力值都是 $$$0$$$，Chiaro 要在施加若干次魔法后使得第 $$$i$$$ 个魔法球最终有 $$$a_i$$$ 的魔力值。然而 Chiaro 作为见习魔法少女掌握的魔力知识很少，她只会两种魔法，而且每种魔法都会消耗一定的体力：

  • 将任意一个魔法球增加 $$$1$$$ 的魔力值，这会消耗她 $$$x$$$ 点体力。
  • 选择任意区间 $$$[l,r]$$$，将第 $$$l$$$ 个到第 $$$r$$$ 个共 $$$r-l+1$$$ 个魔法球的魔力值翻倍，这会消耗她 $$$y$$$ 点体力。

很显然，Chiaro 一定可以只用上述两种魔法若干次来完成这项测试。不过这场魔法使考试才刚刚开始，后面还有很多更困难的测试项目，所以 Chiaro 想用尽可能少的体力完成这个测试，请你帮她算出最少用多少体力可以完成这个测试。

Input

第一行三个非负整数 $$$n,x,y(1\leq n\leq 3\times 10^5,0\leq x,y\leq 10^7)$$$。

接下来一行 $$$n$$$ 个非负整数表示序列 $$$a_1,a_2,\cdots,a_n(0\leq a_i\leq 10^9)$$$。

Output

一行一个整数，表示消耗的最少体力值。

Examples
Input
6 1 1
1 1 4 5 1 4
Output
9
Input
5 2 5
10 7 9 0 3
Output
32