Metro

Pafnutiy wants to use the metro to reach his destination.

To pass through a turnstile, he must use a special SLON card (Subterranean Lowcost Orientational Network). Each card has a non-negative integer balance, the number of burles recorded on it. If a card has at least $k$ burles, it can pass the turnstile, and its balance then decreases by $k$. If the balance is less than $k$, the card cannot be used for the turnstile.

Initially, Pafnutiy has $n$ cards, and card $i$ has balance $a_i$. He has also saved $p$ burles and can distribute this money among the cards in any way. Formally, if he adds $add_i \ge 0$ burles to card $i$, then $add_1 + add_2 + \ldots + add_n \le p$ must hold. Money cannot be moved between cards. A card balance grows only from part of these $p$ burles and shrinks only when the card passes the turnstile.

Find the maximum number of times Pafnutiy can ride the metro if he distributes the $p$ burles optimally.

The first line contains three integers $n$, $p$, and $k$ ($1 \leq n \leq 10^5$, $0 \leq p \leq 10^{18}$, $1 \leq k \leq 10^9$): the number of cards, the saved amount, and the fee for one passage.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$): the card balances.

Print one integer: the maximum number of times Pafnutiy can ride the metro.

In the first example, Pafnutiy can initially ride only 3 times. But if he adds 1 burle to the first, second, or third card, he can ride 4 times.

In the second example, 1000 burles are only enough to bring the balances of both cards to 2000 burles.