$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)$ km/시다.

나쁜 운전 경험 뒤 충돌을 싫어하며 극도로 피한다. 앞의 젖소 한 마리마다 $i$는 $D$ $(0 \le D \le 5,000)$ km/시 감속하며 $0$ 아래로 가지 않는다. 앞에 $K$마리면 $\max(S_i - D K, 0)$이다. 바로 앞보다 빨라도 간격이 충분해 이 감속 뒤 충돌하지 않는다.

Cowtopia 법은 최소 $L$ $(1 \le L \le 1,000,000)$ km/시를 요구해 규칙을 따르면 일부는 못 달린다. 법을 지키며 달릴 최대 수를 구하라.

입력

• $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