G. Укрепление стен
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Замок короля Темура в осаде: за стенами города появился монстр с когтистыми лапами. Чтобы изгнать монстра, волшебнику замка Эмилю потребуется много времени на произнесение отпугивающего заклинания, поэтому он просит короля сдерживать монстра как можно дольше.

Монстра задержит стена замка, которая поделена на $$$n$$$ равных по ширине частей, пронумерованных от $$$1$$$ до $$$n$$$. У каждой части стены есть своя высота $$$h_i$$$. Для того, чтобы проникнуть в замок, монстру придётся уничтожить всю стену. Уничтожение стены происходит следующим образом: монстр (у которого ровно $$$k$$$ когтей на лапах) подходит к некоторой части стены (не расходуя на это времени) и, если высота части стены делится на $$$k$$$, мгновенно эту часть уничтожает (снижает высоту до 0). В противном случае он тратит $$$1$$$ минуту времени, чтобы уменьшить высоту этой части с $$$h_i$$$ до $$$\lfloor \frac{h_i}{k} \rfloor$$$ (деление с округлением до целого вниз). Монстр повторяет эту процедуру, пока вся стена не окажется уничтожена, т.е. высота всех частей не окажется равной нулю.

Помимо стены, у Темура есть $$$m$$$ свитков с заклинаниями мощности $$$c$$$. Темур может использовать каждый из свитков, чтобы увеличить высоту одной (любой) части стены на выбранное им значение от $$$1$$$ до $$$c$$$. При этом на каждую часть стены магия подействует не более одного раза, а применять свитки можно только до того, как монстр начнёт ломать стену.

Помогите королю Темуру определить, какое наибольшее число минут сможет сдерживать стена монстра после её укрепления.

Входные данные

В первой строке через пробел записаны два целых числа: $$$n, k$$$ $$$(1 \le n \le 10^5; 2 \le k \le 10^4)$$$ — количество частей стены и когтей на лапах монстра соответственно.

Во второй строке через пробел записаны $$$n$$$ целых чисел $$$h_i$$$ $$$(0 \le h_i \le 10^9)$$$ — высоты частей стены.

В третьей строке через пробел записаны два целых числа: $$$m, c$$$ $$$(0 \le m \le n; 1 \le c \le 10^9)$$$ — количество свитков и их мощность.

Выходные данные

Выведите единственное число — максимальное время в минутах, которое стена сможет сдерживать монстра.

Примеры
Входные данные
5 2
1 1 1 2 2
3 1
Выходные данные
7
Входные данные
5 2
1 1 1 2 2
3 4
Выходные данные
8
Входные данные
4 9
10 85 9 3
0 7
Выходные данные
4
Примечание

Разберём третий пример:

  • На первую часть стены монстр тратит две минуты. Так как $$$10$$$ не делится на $$$9$$$, то монстр за одну минуту уменьшает высоту до $$$1=\lfloor \frac{10}{9} \rfloor$$$. И ещё минуту он тратит, чтобы уменьшить высоту до $$$0=\lfloor \frac{1}{9} \rfloor$$$.
  • На вторую часть стены монстр тратит одну минуту. Так как $$$85$$$ не делится на $$$9$$$, то монстр за одну минуту уменьшает высоту до $$$9=\lfloor \frac{85}{9} \rfloor$$$. Теперь высота делится на $$$9$$$, поэтому он мгновенно разрушает эту часть стены.
  • Третью часть стены монстр уничтожает мгновенно, ведь $$$9$$$ делится на $$$9$$$.
  • На четвёртую часть стены монстр тратит одну минуту. Так как $$$3$$$ не делится на $$$9$$$, то монстр за одну минуту уменьшает высоту до $$$0=\lfloor \frac{3}{9} \rfloor$$$.

Итого, монстр разрушает стену за $$$4=2+1+0+1$$$ минуты, причём король Темур никак не может увеличить это время, ведь волшебных свитков нет.