提示: 欢迎访问OurACM平台。
Problem 1625 Revival's car

Accept: 39    Submit: 88
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

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

There are multiple tests. For each test, there are two parts.

  • * Line 1: Four space-separated integers: N, M, D, and L
  • * Lines 2..N+1: Line i+1 describes cow i's initial speed with a single integer: S_i

Output

For each test, output a single integer representing the maximum number of cows that can use the highway.

Sample Input

3 1 1 5 5 7 5

Sample Output

2

Hint

INPUT DETAILS:

There are three cows with one lane to drive on, a speed decrease of 1, and a minimum speed limit of 5.

OUTPUT DETAILS:

Two cows are possible, by putting either cow with speed 5 first and the cow with speed 7 second.

Source

Summer Training Qualification I

Submit  Back  Status  Discuss