صممت Bessie لعبة فيديو تعتقد أنها ستكون النجاح الكبير القادم: «Angry Cows». الفكرة التي تراها أصلية تمامًا هي إطلاق الأبقار بالمقلاع إلى مشهد أحادي البعد فيه رزم قش بنقاط على خط الأعداد. تهبط البقرة بقوة تكفي لتفجير الرزم القريبة، والهدف تفجيرها كلها بمجموعة أبقار.

توجد $N$ رزم في مواقع صحيحة مختلفة $x_1, x_2, \ldots, x_N$. إذا أطلقت بقرة بقوة $R$ وهبطت عند $x$، أحدثت انفجارًا نصف قطره $R$ يدمر كل الرزم ضمن $x-R \ldots x+R$.

يتوفر $K$ من الأبقار، كل منها بالقوة نفسها $R$. أوجد أصغر قيمة صحيحة لـ$R$ تسمح لهذه الأبقار $K$ بتفجير كل الرزم.

الإدخال

يحتوي السطر الأول على $N$ ($1 \leq N \leq 50,000$) و$K$ ($1 \leq K \leq 10$). تحتوي الأسطر $N$ الباقية على الأعداد الصحيحة $x_1 \ldots x_N$، كل منها ضمن $0 \ldots 1,000,000,000$.

الإخراج

أخرج أقل قوة إطلاق $R$ لكل بقرة لتفجير جميع الرزم.

أمثلة

الإدخال 1

7 2
20
25
18
8
10
3
1

الإخراج 1

5

مؤلف المسألة: Brian Dean