Giảm cân

Sau kì nghỉ Tết, mặc dù đã cố gắng giảm thiểu tối đa lượng chất béo hấp thụ, nhưng cân nặng của An vẫn tăng lên đáng kể. An không quá chăm chút về ngoại hình nhưng vẫn quyết định giảm cân để có một cơ thể khỏe mạnh. Vì thế An lên kế hoạch tập luyện để giảm cân.
Kế hoạch ban đầu được An đưa ra gồm $N$ buổi tập luyện, buổi tập luyện thứ $i$ có cường độ là $M_i$ ($M_i$ là số nguyên), buổi tập luyện sau luôn có cường độ tập luyện lớn hơn buổi trước nó. Gọi “độ khó” của bản kế hoạch là chênh lệch lớn nhất về cường độ tập luyện giữa hai buổi liền nhau bất kì.
Nhìn vào bản kế hoạch, An cảm thấy chưa hoàn hảo nên muốn cải thiện bằng cách chèn thêm $K$ buổi tập luyện sao cho sau khi chèn vẫn đảm bảo buổi tập luyện sau luôn có cường độ tập luyện lớn hơn buổi tập trước và “độ khó” của bản kế hoạch là nhỏ nhất có thể.
Bạn hãy giúp An tìm “độ khó” của bản kế hoạch hoàn hảo.

• Dòng 1: Hai số nguyên $N, K$. Trong đó, $N$ là số buổi tập luyện ($2 \le N \le 10^5$); $K$ là số buổi cần chèn thêm ($1 \le K \le 10^5$);
• Dòng 2: Ghi $N$ số nguyên $M_1, M_2, \dots, M_N$ với $M_i$ là cường độ tập luyện của buổi thứ $i$ ($1 \le M_i \le 10^9$; $1 \le i \le N$).

• Một số nguyên duy nhất là “độ khó” của bản kế hoạch hoàn hảo.

• Subtask 1 (50% điểm): $K = 1$; $2 \le N \le 300$.
• Subtask 2 (50% điểm): Không có ràng buộc bổ sung.