Метро

Пафнутий решил использовать метро, чтобы достичь своей цели.

Чтобы пройти через турникет, надо использовать специальную карточку SLON (Subterranean Lowcost Orientational Network). У каждой карточки есть неотрицательный целый баланс --- количество бурлей, которые записаны на карточке. Если на карточке есть хотя бы $k$ бурлей, то пройти через турникет возможно, после чего баланс карточки уменьшается на $k$ бурлей. Если же на карточке меньше $k$ бурлей, то Пафнутий не сможет ей воспользоваться, чтобы пройти через турникет.

Изначально у Пафнутия есть $n$ карточек, баланс карточки с номером $i$ составляет $a_i$ бурлей. Также Пафнутий накопил $p$ бурлей и может как угодно распределить эти деньги между карточками. Формально, пусть Пафнутий к балансу карточки с номером $i$ добавил $add_i \ge 0$ бурлей, тогда должно выполняться условие $add_1 + add_2 + \ldots + add_n \le p$. Возможности перераспределять деньги между карточками нет, то есть баланс карточки может увеличиваться только за счет какой-то части из этих $p$ бурлей и уменьшаться только при проходе через турникет.

Пафнутий не очень любит математику. Помогите ему определить, какое максимальное количество раз он сможет поехать на метро, если распределит $p$ бурлей по карточкам оптимально.

В первой строке заданы три целых числа $n$, $p$ и $k$ ($1 \leq n \leq 10^5$, $0 \leq p \leq 10^{18}$, $1 \leq k \leq 10^9$) --- количество карточек, накопленная сумма и плата за один проход через турникет, соответственно.

Во второй строке задано $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$) --- балансы карточек.

Выведите одно целое число --- максимальное количество раз, которое Пафнутий сможет поехать на метро.

В первом примере из условия изначально можно поехать только 3 раза. Но если добавить 1 бурль на первую, вторую или третью карточку, то Пафнутий сможет поехать на метро 4 раза.

Во втором примере 1000 бурлей хватит только для того, чтобы сделать баланс обеих карточек равным 2000 бурлям.