COWCAR  Cow Cars
N (1 ≤ N ≤ 50,000) cows conveniently numbered 1, ..., N are driving in separate cars along a highway in Cowtopia. Cow i can drive in any of M different high lanes (1 ≤ M ≤ N) and can travel at a maximum speed of S_{i} (1 ≤ S_{i} ≤ 1,000,000) km/hour.
After their other bad driving experience, the cows hate collisions and take extraordinary measures to avoid them. On this highway, cow i reduces its speed by D (0 ≤ D ≤ 5,000) km/hour for each cow in front of it on the highway (though never below 0 km/hour). Thus, if there are K cows in front of cow i, the cow will travel at a speed of max(S_{i}  D*K, 0). While a cow might actually travel faster than a cow directly in front of it, the cows are spaced far enough apart so crashes will not occur once cows slow down as described.
Cowtopia has a minimum speed law which requires everyone on the highway to travel at a a minimum speed of L (1 ≤ L ≤ 1,000,000) km/hour, so sometimes some of the cows will be unable to take the highway if they follow the rules above. Write a program that will find the maximum number of cows that can drive on the highway while obeying the minimum speed limit law.
Input
The first line contains the four integers N, M, D, and L. For the next N lines, line i+1 contains the integer S_{i}.
Output
Print a single integer denoting the maximum number of cows that can take the highway.
Example
Input: 3 1 1 5 5 7 5 Output: 2
We can obtain two cows by putting either cow with speed 5 first and the cow with speed 7 second.
hide comments
mazenmayman:
20160825 14:33:24
Wow, I was almost sure it will get TLE but AC on first time! :D 

Deepak Gupta:
20140921 10:27:48
int also works. Depends on your approach. 

Ghost Of Perdition:
20130902 23:24:33
why long long


mala da.... annamala:
20130717 09:30:20
Use long long....Costed me 2 wa's...


Anuj_LuckFove!:
20121229 19:08:16
the description is just fine, though it could have been better...anyway the problem is simple enough... 

saurabh kushwaha:
20121014 10:18:59
ques... language is improper!!!!! 
Added by:  Neal Wu 
Date:  20080522 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 
Resource:  USACO Open 2008 