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