Note

This problem shares its problem setting with Problem B. We recommend reading both problem statements beforehand.

Problem Statement

You are fighting $N$ monsters. The monsters are numbered $1, 2, 3, \dots N$, and the health of the $i$-th monster is $H_i$.

You can use Spell A, described below, up to $A$ times, and Spell B up to $B$ times.

Spell A: Choose $1$ monster and reduce its health by $X$.




Spell B: Reduce the monsters' health in ascending order of their numbers so that their health becomes $0$, reducing health by $Y$ in total. More precisely, the following effect occurs.

Let $P$ be the total amount of health that Spell B can reduce. Immediately after Spell B is used, $P = Y$.

Let $H_1', H_2', \dots H_N'$ be the monsters' health immediately before Spell B is used. In the order $i = 1, 2, \dots N$, do the following.

• If $H_i' ≤ 0$, do nothing.
• If $H_i' > 0$, reduce the health of monster $i$ by $D = \mathrm{min}(P, H_i')$. Then, reduce the value of $P$ by $D$.

If Spell B is used multiple times, it is initialized to $P = Y$ each time.

Thinking that the strength of just $1$ person cannot bring the health of all monsters down to $0$ or less, you decide to choose $1$ non-negative integer $K$ and ask your magician friend to reduce the health of every monster by $K$ in advance.

Find the minimum value of $K$ such that, after the health has been reduced, you can bring the health of all monsters down to $0$ or less by using the $2$ types of spells.

Constraints

• All inputs are integers.
• $ 1 \leq N \leq 10^5 $
• $ 0 \leq A, B \leq 10^5 $
• $ 1 \leq X, Y \leq 10^9 $
• $ 1 \leq H_i \leq 10^9 $

Input

$N$ $A$ $B$ $X$ $Y$
$H_1$ $H_2$ $\dots$ $H_N$

Output

Print the minimum non-negative integer $K$ such that the health of all monsters can be brought down to $0$ or less using Spell A and Spell B. Print a newline at the end.

Sample

3 1 1 8 9
14 13 5

5

5 2 1 85 81
50 98 96 21 69

20

15 1 6 4571 4268
6955 1118 6093 7840 4109 2330 5533 2202 2844 1595 590 5776 8883 7632 3759

2934