Метро

문제

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

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

Изначально у Пафнутия есть $nn$ карточек, баланс карточки с номером $ii$ составляет $a_{i}a\_i$ бурлей. Также Пафнутий накопил $pp$ бурлей и может как угодно распределить эти деньги между карточками. Формально, пусть Пафнутий к балансу карточки с номером $ii$ добавил $ad{d}_i\ge 0add\_i\; \backslash ge\; 0$ бурлей, тогда должно выполняться условие $ad{d}_1+ad{d}_2+\dots +ad{d}_n\le padd\_1\; +\; add\_2\; +\; \backslash ldots\; +\; add\_n\; \backslash le\; p$. Возможности перераспределять деньги между карточками нет, то есть баланс карточки может увеличиваться только за счет какой-то части из этих $pp$ бурлей и уменьшаться только при проходе через турникет.

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

입력

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

Во второй строке задано $nn$ целых чисел $a_1,a_2,\dots ,a_{n}a\_1,\; a\_2,\; \backslash ldots,\; a\_n$ ($0\le a_i\le {10}^{9}0\; \backslash leq\; a\_i\; \backslash leq\; 10^9$) --- балансы карточек.

출력

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

힌트

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

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