$N$ $(1 \le N \le 50,000)$ коров с номерами $1,\ldots,N$ едут каждая на автомобиле по шоссе Cowtopia. Корова $i$ выбирает любую из $M$ полос $(1 \le M \le N)$, максимум скорости $S_{i}$ $(1 \le S_{i} \le 1,000,000)$ км/ч.

После плохого опыта они ненавидят столкновения и тщательно избегают их. За каждую корову впереди на шоссе корова $i$ снижает скорость на $D$ $(0 \le D \le 5,000)$ км/ч, не ниже $0$. Если впереди $K$, скорость $\max(S_i - D K, 0)$. Даже если быстрее непосредственно передней коровы, расстояния достаточны, чтобы после снижения не было аварий.

Закон Cowtopia требует минимум $L$ $(1 \le L \le 1,000,000)$ км/ч, поэтому некоторые коровы не смогут ездить по этим правилам. Найдите максимум коров на шоссе с соблюдением закона.

Входные данные

• Строка $1$: целые $N$, $M$, $D$, $L$ через пробел.

• Строки $2,\ldots,N+1$: строка $i+1$ описывает начальную скорость коровы $i$ целым $S_{i}$.

Выходные данные

• Строка $1$: целое, максимум коров на шоссе.

Примеры

Входные данные 1

3 1 1 5
5
7
5

Выходные данные 1

2

Примечание

Три коровы, одна полоса, снижение $1$, минимум $5$.

Можно две: любую со скоростью $5$ первой, со скоростью $7$ второй.

Автор задачи: Neal Wu, 2007