J. Flame Strike 2
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Nailong is killing monsters in the game. This is a turn-based game, and he encounters $$$n$$$ monsters with health points of $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ respectively.

Each turn, Nailong can cast one of the following skills once:

  • Fireball: Select a monster, deal $$$x$$$ damage to it, and consume $$$a$$$ mana points.
  • Flamestrike: Deal $$$y$$$ damage to all monsters, and consume $$$b$$$ mana points.

When a monster takes damage, an equal amount of health points will be deducted. If its health points are less than or equal to $$$0$$$, the monster will be killed. Nailong wins the battle when all $$$n$$$ monsters are killed.

Please help Nailong plan his skill usage to minimize the mana consumed while winning the battle, and calculate the minimum mana required.

Input

Each test case in this problem contains only one set of test data.

The first line contains 5 integers $$$n$$$, $$$x$$$, $$$y$$$, $$$a$$$, $$$b$$$ ($$$1 \le n, x, y, a, b \le 2 \times 10^6$$$), respectively representing the number of monsters, the damage of Fireball and Flame Strike, and their mana consumption.

The next line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \le a_i \le 10^7$$$), representing the health points of the monsters.

Output

Output a single line with an integer, representing the minimum mana Nailong needs to consume to win the battle.

Examples
Input
4 10 8 5 7
9 17 23 40
Output
31
Input
5 3 1 2 5
1 2 3 4 10
Output
17
Note

For the first sample, A feasible skill usage plan for Nailong is to use Flamestrike 7 times, and then use Fireball once on the last monster.

This way, the other monsters take $$$7 \times 3 = 21$$$ damage, and the last monster takes $$$10 + 7 \times 3 = 31$$$ damage, so they are all killed.

The mana consumption is $$$7 \times 4 + 6 \times 1 = 34$$$ points, and it can be proven that this is optimal.