Konfrans#10396
Farmer John öz fermasında yeni bir mal-qara otyemə konfransı təşkil edir!
Dünyanın hər yerindən inəklər konfransda iştirak edib ot yemək üçün yerli hava limanına gəlirlər. Daha dəqiq desək, hava limanına inək gəlir və -ci inək t_i~(0 \le t_i \le 10^9) vaxtında gəlir. Farmer John inəkləri hava limanından daşımaq üçün avtobus ayırmışdır. Hər avtobus ən çoxu inək tuta bilər. Farmer John avtobuslarla birlikdə hava limanında gözləyir və gələn inəkləri avtobuslara təyin etmək istəyir. Avtobusa təyin olunmuş sonuncu inək gələn kimi avtobus yola düşə bilər. Farmer John yaxşı ev sahibi olmaq istədiyi üçün inəklərin hava limanında çox uzun müddət gözləməsini istəmir. İnəyin gözləmə müddəti onun avtobusunun yola düşmə vaxtı ilə onun gəlmə vaxtı arasındakı fərqdir. Əgər Farmer John avtobuslarını optimal şəkildə əlaqələndirsə, bütün inəklər üzrə maksimum gözləmə müddətinin ən kiçik mümkün dəyəri nə olar?
Zəmanət verilir ki, m \cdot c \ge n.
Birinci sətirdə üç tam ədəd verilir: , və c~(1 \le n \le 10^5, 1 \le m \le 10^5, 1 \le c \le n). İkinci sətirdə tam ədəd — inəklərin gəlmə vaxtları verilir.
Bir tam ədəd — bütün inəklər üzrə maksimum gözləmə müddətinin minimum mümkün dəyərini çap edin.
Nümunə 1
Əgər vaxtında gələn iki inək birinci avtobusa, və vaxtlarında gələnlər ikinci avtobusa, və vaxtlarında gələnlər isə üçüncü avtobusa minsələr, onda ən uzun gözləmə müddəti zaman vahidi olar (10-cu vaxtda gələn inək 10-dan 14-ə qədər gözləyir).