Genshin

După o zi grea de muncă, pentru a se relaxa, Mika se joacă Genshin Impact. Astăzi, are loc un event special în urma căruia ea va putea cumpăra echipamentul legendar pe care și l-a dorit de mult timp.

Acest event se poate juca doar împreună cu încă un prieten, așa că după ce Mika și-a găsit un partener de joc, ei s-au înregistrat la event și au citit instrucțiunile.

Eventul presupune înfrângerea a $N$ monștri numerotați de la $1$ la $N$, iar fiecare din acești monștri au un număr de puncte de viață $hp_i$. Acești monștri trebuie atacați până când aceștia sunt eliminați (un monstru se consideră eliminat atunci când punctele lui de viață devin $0$ sau mai mici decât $0$). Echipamentul Mikăi îi oferă acesteia $X$ puncte de atac, iar echipamentul coechipierului ei îi oferă acestuia $Y$ puncte de atac.

Fiecare luptă a echipei formată din Mika și coechipierul ei are loc în ture, în care atât Mika cât și echipierul ei vor ataca același monstru până când acesta este eliminat complet. În fiecare tură, Mika este cea care începe să atace monstrul curent, oferindu-i daune în valoare de $X$ puncte de viață, urmată de coechipierul său care îi oferă monstrului daune în valoare de $Y$ puncte de viață.

Astfel, dacă monstrului i-au mai rămas $V$ puncte de viață, atunci după atacul Mikăi el va rămâne cu $V − X$ puncte de viață, și respectiv, $V − X − Y$ puncte de viață după atacul coechipierului Mikăi (în cazul în care monstrul nu a fost înfrânt de Mika după lovitura acesteia).

Pentru acest event, jucătorii trebuie să obțină niște monede speciale pe care o să le valorifice mai târziu. Un jucător va primi o monedă specială daca acesta este cel care aplică lovitura finală unui monstru.

Cu alte cuvinte:

• dacă Mika aplică o lovitură monstrului, iar după ce îi aplică daune în valoare de $X$ puncte de viață, monstrul rămâne cu $0$ sau mai puține puncte de viață, ea va câștiga o monedă specială.
• dacă coechipierul Mikăi aplică o lovitură monstrului, iar după ce îi aplică daune în valoare de $Y$ puncte de viață, monstrul rămâne cu $0$ sau mai puține puncte de viață, acesta va câștiga o monedă specială.

Caracterul Mikăi are o abilitate specială care îi permite să își distragă coechipierul, dar ea o poate folosi în total doar de $D$ ori pe parcursul eventului. Ea realizează că poate să folosească această abilitate să își facă coechipierul să nu își efectueze tura și să obțină, în final, mai multe monede.

Totuși, Mika nu știe cum să facă asta în mod optim, așa că vă roagă pe voi să o ajutați să afle care este numărul maxim de monede speciale pe care ea le poate obține aplicând maxim $D$ abilități de distragere.

Date de intrare

Fișierul genshin.in conține:

• Linia 1: $4$ numere naturale care corespund valorilor $N, X, Y$ și $D$ care au semnificația specificată în enunț;
• Linia 2: $N$ numere naturale $hp_1, hp_2, ..., hp_N$ , unde $hp_i$ semnifică numărul de puncte de viață pe care monstrul $i$ îl are la începutul eventului.

Date de ieșire

Fișierul genshin.out va avea o singură linie care va conține numărul maxim de monede speciale pe care Mika le poate obține dacă folosește optim cele maxim $D$ abilități de distragere.

Restricții și precizări

• $1 \leq N \leq 2 \cdot 10^5$
• $1 \leq X, Y \leq 10^9$
• $1 \leq D \leq 10^9$
• $1 \leq hp_i \leq 10^9$, unde $1 \leq i \leq N$
• În momentul în care Mika și coechipierul ei vor începe să se lupte cu un monstru nou, Mika va fi mereu cea care va aplica prima lovitură.
• Abilitatea de distragere poate fi aplicată de mai multe ori în lupta cu un același monstru (vezi exemplul $2$).
• În momentul în care Mika își foloses,te abilitatea de distragere, ea va anula lovitura coechipierului său și va forța începerea unei noi ture.

Exemplul 1

genshin.in

7 4 2 1
1 2 7 6 3 5 4

genshin.out

6

Explicație

Mika poate alege să folosească abilitatea de distragere (de altfel, singura, $D$ având valoarea $1$) în momentul în care ei se luptă cu monstrul $4$ sau monstrul $6$ pentru a garanta numărul optim de monede speciale.

Exemplul 2

genshin.in

6 2 3 3
7 1 10 50 12 8

genshin.out

5

Explicație

Mika poate alege să folosească abilitatea de distragere de $2$ ori pentru monstrul $3$ și o singură dată pentru monstrul $6$, în total această abilitate fiind folosită de $3$ ori.