Problem K
Kaffiskömmtun
Languages
en
is
One of the most important resources to a university is coffee. It is of the utmost importance that this resource is utilized to its maximum potential.
To this end, coffee has to be prepared regularly. This preparation has to be timed correctly, since computer science professors are quite busy. If there is no coffee ready when a computer scientist goes to the break room, they will have to leave without coffee. They are, however, always willing to help and can prepare a fresh batch of coffee, even after pouring themselves a cup. Once preparation has started, it takes $T$ seconds for the fresh batch of coffee to be ready. A fresh batch of coffee is enough for $C$ cups of coffee.
What is the maximum number of professors that can have a cup of coffee if we plan perfectly? Note that sometimes it is optimal to pour leftover coffee and prepare a fresh batch, even though it is a sinful waste of resources. Initially there is no coffee prepared.
Input
The first line of input contains three integers $N$, the number of professors taking a coffee break, where $1 \leq N \leq 10^6$, $C$, the number of cups a batch can fill, where $1 \leq C \leq 500$, and $T$, the number of seconds it takes for a new batch to be ready, where $1 \leq T \leq 10^9$. Finally there is a single line with $N$ integers $1 \leq t_1 \leq t_2 \leq \dots \leq t_ N \leq 10^9$, the times at which the professors take their coffee breaks.
Output
Print the maximum number of professors that can have coffee when they go on break.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 2 10 1 8 12 23 25 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 3 4 1 4 5 6 8 10 12 |
4 |
