Bessie thiết kế trò chơi điện tử cô nghĩ sẽ là cú hit lớn tiếp theo: "Angry Cows". Ý tưởng cô cho là hoàn toàn nguyên gốc là dùng ná bắn bò vào cảnh một chiều với kiện cỏ ở các điểm trên trục số. Mỗi bò đáp xuống đủ mạnh để làm nổ kiện gần đó. Mục tiêu là dùng các bò làm nổ mọi kiện.

Có $N$ kiện tại các vị trí nguyên phân biệt $x_1, x_2, \ldots, x_N$. Bò bắn với sức $R$ đáp tại $x$ tạo vụ nổ bán kính $R$, phá mọi kiện trong $x-R \ldots x+R$.

Có $K$ bò để bắn, mỗi con cùng sức $R$. Tìm giá trị nguyên nhỏ nhất của $R$ để dùng $K$ bò làm nổ mọi kiện.

Dữ liệu vào

Dòng đầu chứa $N$ ($1 \leq N \leq 50,000$) và $K$ ($1 \leq K \leq 10$). $N$ dòng còn lại chứa số nguyên $x_1 \ldots x_N$, mỗi số trong $0 \ldots 1,000,000,000$.

Dữ liệu ra

In sức bắn nhỏ nhất $R$ cho mỗi bò để làm nổ mọi kiện.

Ví dụ

Dữ liệu vào 1

7 2
20
25
18
8
10
3
1

Dữ liệu ra 1

5

Tác giả bài toán: Brian Dean