Joe loves sleeping. He loves it so much that he'll take naps whenever and wherever possible. He is currently on a car ride with his parents, which will be ~N~ minutes long. During the trip, there will be ~M~ events at distinct times ~t_1, t_2, \ldots, t_M~ that will wake Joe up if he is sleeping during those times. Joe plans to take up to ~K~ naps during these ~N~ minutes, and since he loves uniformity, he wants them all to be of the same length. Joe wishes to know the maximum number of minutes he can nap during the ride.
~1 \leq N,K \leq 10^8~
~1 \leq M \leq \min(50\,000, N)~
~1 \leq t_i \leq N~
The first line will contain three integers ~N, M~ and ~K~.
The second line will contain ~M~ space separated integers, ~t_1, t_2, \ldots, t_M~.
Output on a single line the maximum number of minutes Joe can sleep.
22 2 5 6 17
The best options is to take four 5-minute long naps during intervals ~[1,5]~, ~[7,11]~, ~[12,16]~, and ~[18,22]~.