Để đảm bảo đủ chỗ và an toàn cho việc cách ly n người tại bệnh viện trong mùa Covid. Bệnh viện K đã tiến hành lập ~m~ phòng cách ly dã chiến trên khu đất dự phòng. Do vị trí của khu đất nên các phòng cách ly này được xây dựng trên một dãy đối diện với khu hành chính. Căn phòng thứ ~i~ được xây dựng tại vị trí ~a_i~ tính từ vị trí đầu khu đất. Do tính chất lây lan của dịch bệnh và để đảm bảo an toàn cho những người bị cách ly Ban giám đốc bệnh viện quyết định bố trí cho ~n~ người vào ~m~ phòng cách ly (mỗi phòng bố trí ~1~ người) sao cho khoảng cách tối thiểu giữa hai người trong số các người bị cách ly càng lớn càng tốt.

Yêu cầu: Em hãy lập trình giúp Ban giám đốc tìm cách bố trí ~n~ người này vào ~m~ phòng sao cho khoảng cách tối thiểu giữa hai người là lớn nhất.

Dữ liệu vào

Cho file COVID.INP có dạng:

• Dòng thứ nhất ghi ~2~ số nguyên ~m~ và ~n~ ~( 2 ≤ n ≤ m ≤ 10^5)~
• Dòng thứ hai ghi ~m~ số nguyên ~a_1, a_2, …, a_N~ ~( 0 < a_1 < a_2 < … < a_N ≤ 10^6)~

Các số trên cùng một dòng cách nhau một dấu cách.

Dữ liệu ra

Ghi vào file COVID.OUT một số nguyên duy nhất là khoảng cách tối thiểu lớn nhất khi bố trí để bố trí hết ~n~ người cần cách ly vào ~m~ phòng.

Ví dụ

COVID.INP

10 4
2 3 7 8 12 15 19 30 32 45

COVID.OUT

13

Ràng buộc