On a certain route, buses are initially evenly spaced; however, due to the inconsistent traffic flow, one bus can get slightly delayed. As that bus becomes increasingly crowded due to the greater number of passengers at each stop, it gets delayed even further while the bus behind it catches up. This leads to buses travelling in packs where the first bus is full and the last one is almost empty.
As the buses (and especially the passengers) get jammed, one solution is to make the almost empty buses wait for a certain number of minutes so that there can be a reasonable gap.
Given a list of buses and the length of time that it is away from the terminus, find the minimum number of ~M~-minute breaks required so that all buses will have headways (the length of time between buses) of at most ~H~ minutes.
Each bus has the choice of taking any number of ~M~-minute breaks, even if it means being overtaken by another bus or waiting until the next day.
The first line of input will contain three space-separated integers, ~N~ ~(1 \le N \le 1\,000)~, which represents the number of buses, ~M~ ~(1 \le M \le 100)~, the duration of one break, and ~H~ ~(1 \le H \le 100)~, the desired headway (length of time between buses).
The next ~N~ lines contain the length of time, ~T~, ~(0 \le T \le 1\,000)~ in minutes, in which the bus is expected to arrive at the terminus. The times will be sorted in ascending order.
Output the minimum number of ~M~-minute breaks that will occur.
It is guaranteed that it will be possible to achieve a headway of at most ~H~ minutes.
5 2 10 1 13 23 35 44
Explanation for Sample Input
The first bus can take two breaks while the second and third buses can take one break each.
All headways are now ~10~ minutes or less, as required.