|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
In a building with $n$ floors some packages have arrived for each department and it is necessary to carry them up to their respective recipients. There are $m$ packages at floor $0$ and each of them has annotated the floor to which it must be sent. For security issues, the elevator can carry at most $k$ packages at the same time. A delivery consists in the following process: select the maximum floor of the delivery, move the elevator to that floor and finally deliver the packages to the current floor and the ones below it (while the elevator goes down to floor $0$). In each delivery of the packages, the elevator must end up at floor $0$. Your task is to find out the optimal strategy to carry all the packages with the minimum number of deliveries.
Input
A line with thee integers $n$, $m$, $k$, the amount of floors, the amount of packages to be delivered and the maximum amount of packages that can be carried in the elevator in each moment respectively. Then a line with $m$ integers. The integer $a_i$ is the floor to which the i-th package must be sent.
Limits: $1 \leq n, m, k \leq 100000$, $1 \leq a_i \leq n$.
Output
An integer that denotes the minimum number of deliveries to carry up all the packages as it was explained above.
Sample test(s)
Input
5 4 2
1 2 3 4
Output
2
Input
5 4 4
1 3 3 5
Output
1