Cow Cars

There are $N$ ($1 \le N \le 50000$) cows, numbered $1$ through $N$, each driving a separate car along a highway. The highway has $M$ ($1 \le M \le N$) lanes, and every cow may drive in any lane. Cow $i$ has a maximum speed of $S_i$ ($1 \le S_i \le 1000000$) km/h.

To avoid collisions, cow $i$ slows down by $D$ ($0 \le D \le 5000$) km/h for each cow ahead of it in the same lane. So if $K$ cows are ahead of cow $i$ in its lane, that cow travels at $\max(S_i - D \cdot K, 0)$ km/h. The cows are spaced far enough apart that no crashes occur once they slow down this way.

A minimum-speed law requires every cow on the highway to travel at a speed of at least $L$ ($1 \le L \le 1000000$) km/h, so some cows may be unable to use the highway. Find the maximum number of cows that can drive on the highway while obeying the minimum-speed law.

• Line 1: four space-separated integers $N$, $M$, $D$, and $L$.
• Lines $2$ to $N+1$: line $i+1$ contains a single integer $S_i$, the maximum speed of cow $i$.

• A single integer: the maximum number of cows that can use the highway.

With three cows, one lane, a per-cow slowdown of $1$, and a minimum speed of $5$, at most two cows can drive. Put a cow of speed $5$ first (it travels at $5$) and the cow of speed $7$ second (it travels at $7 - 1 = 6$); both meet the minimum speed of $5$.