Maximizing Cows on the Highway

Cowtopia's highway is a unique roadway where N cows (numbered from 1 to N) drive in separate cars. Each cow has a maximum speed of S_i km/hour and may choose any of M available lanes. To avoid collisions, when cow i is driving in a lane, its speed is reduced by D km/hour for every cow in front of it in that same lane (but the speed will not drop below 0 km/hour). Hence, if there are K cows ahead of cow i in its lane, its traveling speed becomes:

\( \max\{S_i - D \times K,\, 0\} \)

Moreover, Cowtopia enforces a law that demands any vehicle on the highway must be traveling at least at a speed of L km/hour. Some cows may thus be forced to stay off the highway if they cannot meet this minimum speed, even when choosing the best lane.

The task is to determine the maximum number of cows that can drive on the highway while obeying the minimum speed law. Formally, a cow with maximum speed S may occupy a position p (where 0 indicates the front of a lane) in a lane only if:

\( S - D \times p \ge L \)

You are allowed to decide the order in which cows line up in each lane (each lane is independent) and assign cows to lanes arbitrarily. When D > 0, the condition for a cow to take the p-th position is equivalent to requiring:

\( p \le \left\lfloor\frac{S - L}{D}\right\rfloor \)

For the special case when D = 0, a cow can join the highway if and only if S \( \ge L \), regardless of its position in the lane.

Write a program that, given N, M, D, L and the list of maximum speeds for the cows, computes the maximum number of cows that can be assigned to the highway while satisfying the speed law.

inputFormat

The first line contains four space-separated integers: N (the number of cows), M (the number of lanes), D (the speed reduction factor), and L (the minimum required speed in km/hour).

The second line contains N space-separated integers: S₁, S₂, ..., S_N representing the maximum speed of each cow.

outputFormat

Output a single integer, the maximum number of cows that can drive on the highway while obeying the minimum speed law.

sample

5 2 10 30
30 40 50 30 60

3