$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