$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