G. Wall reinforcement
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The castle of King Timur is under siege: a monster with clawed paws has appeared outside the city walls. To banish the monster, the wizard of the castle, Emil, will need a lot of time to cast a repelling spell, so he asks the king to hold the monster back for as long as possible.

The wall of the castle will hold the monster. The wall is divided into $$$n$$$ parts of equal width, numbered from $$$1$$$ to $$$n$$$. Each part of the wall has its own height $$$h_i$$$. To penetrate the castle, the monster will have to destroy the entire wall. The destruction of the wall occurs as follows: the monster (which has exactly $$$k$$$ claws on its paws) approaches a certain part of the wall (without spending time on it) and, if the height of the part of the wall is divisible by $$$k$$$, instantly destroys that part (reduces the height to 0). Otherwise, it takes $$$1$$$ minute to reduce the height of that part from $$$h_i$$$ to $$$\lfloor \frac{h_i}{k} \rfloor$$$ (division rounded down to the nearest integer). The monster repeats this procedure until the entire wall is destroyed, i.e. the height of all parts is reduced to zero.

In addition to the wall, Timur has $$$m$$$ scrolls with spells of power $$$c$$$. Timur can use each of the scrolls to increase the height of one (any) part of the wall by a value chosen by him from $$$1$$$ to $$$c$$$. At the same time, magic will affect no more than one part of the wall, and the scrolls can only be used before the monster starts breaking the wall.

Help King Timur determine the maximum number of minutes the wall can hold the monster after being reinforced.

Input

The first line contains two integers separated by a space: $$$n, k$$$ $$$(1 \le n \le 10^5; 2 \le k \le 10^4)$$$ — the number of parts of the wall and the number of claws on the monster's paws, respectively.

The second line contains $$$n$$$ integers separated by a space: $$$h_i$$$ $$$(0 \le h_i \le 10^9)$$$ — the heights of the parts of the wall.

The third line contains two integers separated by a space: $$$m, c$$$ $$$(0 \le m \le n; 1 \le c \le 10^9)$$$ — the number of scrolls and their power.

Output

Output a single number — the maximum time in minutes that the wall can hold the monster.

Examples
Input
5 2
1 1 1 2 2
3 1
Output
7
Input
5 2
1 1 1 2 2
3 4
Output
8
Input
4 9
10 85 9 3
0 7
Output
4
Note

Let's consider the third example:

  • The monster spends two minutes on the first part of the wall. Since $$$10$$$ is not divisible by $$$9$$$, the monster reduces the height to $$$1=\lfloor \frac{10}{9} \rfloor$$$ in one minute. And he spends another minute to reduce the height to $$$0=\lfloor \frac{1}{9} \rfloor$$$.
  • The monster spends one minute on the second part of the wall. Since $$$85$$$ is not divisible by $$$9$$$, the monster reduces the height to $$$9=\lfloor \frac{85}{9} \rfloor$$$ in one minute. Now the height is divisible by $$$9$$$, so he instantly destroys this part of the wall.
  • The monster instantly destroys the third part of the wall, since $$$9$$$ is divisible by $$$9$$$.
  • The monster spends one minute on the fourth part of the wall. Since $$$3$$$ is not divisible by $$$9$$$, the monster reduces the height to $$$0=\lfloor \frac{3}{9} \rfloor$$$ in one minute.

In total, the monster destroys the wall in $$$4=2+1+0+1$$$ minutes, and King Timur cannot increase this time, since there are no magic scrolls.