Convention#10396
Farmer John sta organizzando una nuova convention bovina per mangiare erba nella sua fattoria!
Mucche da tutto il mondo stanno arrivando all'aeroporto locale per partecipare alla convention e mangiare erba. Nello specifico, mucche arrivano all'aeroporto, e la mucca arriva al tempo t_i~(0 \le t_i \le 10^9). Farmer John ha organizzato autobus per trasportare le mucche dall'aeroporto. Ogni autobus può contenere fino a mucche. Farmer John sta aspettando con gli autobus all'aeroporto e vuole assegnare le mucche in arrivo agli autobus. Un autobus può partire non appena arriva l'ultima mucca assegnata ad esso. Farmer John vuole essere un buon ospite, quindi non vuole che le mucche aspettino troppo tempo all'aeroporto. Il tempo di attesa di una mucca è la differenza tra l'orario di partenza del suo autobus e il suo orario di arrivo. Se Farmer John coordina i suoi autobus in modo ottimale, qual è il più piccolo valore possibile del tempo di attesa massimo su tutte le mucche?
È garantito che m \cdot c \ge n.
La prima riga contiene tre interi , e c~(1 \le n \le 10^5, 1 \le m \le 10^5, 1 \le c \le n). La seconda riga contiene interi — gli orari di arrivo delle mucche.
Stampa un intero — il valore minimo possibile del tempo di attesa massimo su tutte le mucche.
Esempio 1
Se le due mucche arrivate al tempo salgono sul primo autobus, le mucche arrivate ai tempi e sul secondo, e le mucche arrivate ai tempi e sul terzo, allora il tempo di attesa più lungo è di unità di tempo (la mucca arrivata al tempo aspetta dal tempo al tempo ).