Konvansiyon#10396
Farmer John çiftliğinde yeni bir sığır otlama konvansiyonu düzenliyor!
Dünyanın dört bir yanından inekler konvansiyona katılmak ve ot yemek için yerel havaalanına geliyor. Daha spesifik olarak, inek havaalanına varıyor ve numaralı inek t_i~(0 \le t_i \le 10^9) zamanında geliyor. Farmer John, inekleri havaalanından taşımak için otobüs ayarlamıştır. Her otobüs en fazla inek alabilir. Farmer John otobüslerle birlikte havaalanında bekliyor ve gelen inekleri otobüslere atamak istiyor. Bir otobüs, kendisine atanan son inek geldiği anda hareket edebilir. Farmer John iyi bir ev sahibi olmak istediğinden, ineklerin havaalanında çok fazla beklemesini istemiyor. Bir ineğin bekleme süresi, otobüsünün kalkış zamanı ile kendi varış zamanı arasındaki farktır. Eğer Farmer John otobüslerini en iyi şekilde koordine ederse, tüm inekler arasındaki maksimum bekleme süresinin alabileceği en küçük değer nedir?
m \cdot c \ge n olduğu garanti edilmektedir.
İlk satır üç tam sayı içerir: , ve c~(1 \le n \le 10^5, 1 \le m \le 10^5, 1 \le c \le n). İkinci satır, ineklerin varış zamanlarını belirten tam sayı içerir.
Tüm inekler arasındaki maksimum bekleme süresinin alabileceği minimum değeri temsil eden tek bir tam sayı yazdırın.
Örnek 1
Eğer 1. zamanında gelen iki inek ilk otobüse, 3. ve 4. zamanlarında gelen inekler ikinci otobüse, 10. ve 14. zamanlarında gelen inekler ise üçüncü otobüse binerse, en uzun bekleme süresi 4 zaman birimi olur (10. zamanında gelen inek, 10'dan 14'e kadar bekler).