Background

:::epigraph Do you need my help? :::

Problem Description

Nailong is fighting monsters in a turn-based game. He encounters $n$ monsters, whose health values are $h_1, h_2, \dots, h_n$.

In each turn, Nailong can choose to cast exactly one of the following skills once:

• Fireball: Choose one monster, deal $x$ damage to it, and consume $a$ mana from Nailong.
• Flame Storm: Deal $y$ damage to all monsters, and consume $b$ mana from Nailong.

When a monster takes damage, its health is reduced by the same amount. If its health is less than or equal to $0$, the monster is killed. When all $n$ monsters are killed, Nailong wins the battle.

Please help Nailong plan his skill usage so that he wins the battle with the minimum mana cost, and output the minimum mana required.

Input Format

There is only one set of testdata in each test.

The first line contains $5$ integers $n, x, y, a, b\ (1 \le n, x, y, a, b \le 2 \times 10^6)$, representing the number of monsters, the damage of Fireball and Flame Storm, and the mana costs of these two skills.

The next line contains $n$ integers $h_1, h_2, \dots, h_n\ (1 \le h_i \le 10^7)$, representing the health of each monster.

Output Format

Output one line containing one integer, representing the minimum mana cost for Nailong to win the battle.

4 10 8 5 7
9 17 23 40

31

5 3 1 2 5
1 2 3 4 10

17

Hint

Sample 1 Explanation

One feasible plan is to use Flame Storm $3$ times, and then use Fireball $2$ times on the last monster.

Then the other monsters take $8 \times 3 = 24$ damage, and the last monster takes $24 + 10 \times 2 = 44$ damage, so all of them are killed.

The mana cost is $3 \times 7 + 2 \times 5 = 31$, and it can be proven that this is optimal.

Translated by ChatGPT 5