Пафнутий решил использовать метро, чтобы достичь своей цели.
Чтобы пройти через турникет, надо использовать специальную карточку 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$$$) — балансы карточек.
Выведите одно целое число — максимальное количество раз, которое Пафнутий сможет поехать на метро.
5 1 4
7 7 3 4 1
4
2 1000 2000
1299 1701
2
В первом примере из условия изначально можно поехать только 3 раза. Но если добавить 1 бурль на первую, вторую или третью карточку, то Пафнутий сможет поехать на метро 4 раза.
Во втором примере 1000 бурлей хватит только для того, чтобы сделать баланс обеих карточек равным 2000 бурлям.
Тесты к этой задаче состоят из пяти подзадач. Баллы за каждую подзадачу ставятся только при прохождении всех тестов подзадачи и всех тестов необходимых подзадач.
