COWCAR - Cow Cars

no tags 

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 Si (1 ≤ Si ≤ 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(Si - 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 Si.

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: 2016-08-25 14:33:24

Wow, I was almost sure it will get TLE but AC on first time! :D

Deepak Gupta: 2014-09-21 10:27:48

int also works. Depends on your approach.

Ghost Of Perdition: 2013-09-02 23:24:33

why long long
@mala da.... annamala ?

mala da.... annamala: 2013-07-17 09:30:20

Use long long....Costed me 2 wa's...

Anuj_LuckFove!: 2012-12-29 19:08:16

the description is just fine, though it could have been better...anyway the problem is simple enough...

saurabh kushwaha: 2012-10-14 10:18:59

ques... language is improper!!!!!


Added by:Neal Wu
Date:2008-05-22
Time limit:0.165s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:USACO Open 2008