Злі корови (Срібло)#10595
Корова Бессі розробила те, що, на її думку, стане наступною популярною відеогрою: "Angry Cows". Сюжет гри, який Бессі вважає повністю оригінальним, полягає в наступному: гравець запускає корів із рогатки в одновимірну сцену, що складається з безлічі стогів сіна, розташованих у різних точках числової прямої. Кожна корова приземляється з достатньою силою, щоб підірвати стоги сіна, що знаходяться в безпосередній близькості від місця її приземлення. Мета гри — використати декількох корів, щоб підірвати всі стоги сіна.
На числовій прямій розташовано стогів сіна у різних цілочислових точках x_1, x_2, \ldots, x_n. Якщо корову запускають із силою , і вона приземляється в точці , то утворюється вибух радіуса , який знищує всі стоги сіна, розташовані всередині інтервалу [x - r, x + r].
Для запуску доступно корів, причому кожна з них має однакову силу . Визначте мінімальне ціле значення , при якому за допомогою цих корів можна підірвати всі стоги сіна.
У першому рядку містяться два цілих числа n~(1 \le n \le 50000) та k~(1 \le k \le 10). У кожному з наступних рядків міститься ціле число x_i~(0 \le x_i \le 10^9), що задає положення одного зі стогів сіна на числовій прямій.
Виведіть мінімальну силу , з якою необхідно запускати кожну корову, щоб підірвати всі стоги сіна.
Приклад 1