Cô bò Bessie đã thiết kế một trò chơi điện tử mà cô nghĩ sẽ trở thành trò chơi ăn khách tiếp theo: "Angry Cows". Ý tưởng mà cô tin là hoàn toàn nguyên bản như sau: người chơi dùng súng cao su bắn những con bò vào một khung cảnh một chiều gồm các kiện cỏ khô nằm tại nhiều điểm trên một trục số. Mỗi con bò đáp xuống với lực đủ mạnh để làm nổ các kiện cỏ ở gần điểm tiếp đất. Mục tiêu là dùng một nhóm bò để làm nổ tất cả các kiện cỏ.

Có \(N\) kiện cỏ nằm tại các vị trí nguyên phân biệt \(x_1, x_2, \ldots, x_N\) trên trục số. Nếu một con bò được phóng với sức mạnh \(R\) và đáp xuống vị trí \(x\), nó sẽ tạo ra một vụ nổ có "bán kính \(R\)", phá hủy mọi kiện cỏ trong đoạn \(x-R\ldots x+R\).

Có tổng cộng \(K\) con bò để phóng, mỗi con đều có cùng sức mạnh \(R\). Hãy xác định giá trị nguyên nhỏ nhất của \(R\) sao cho có thể dùng \(K\) con bò để làm nổ mọi kiện cỏ trong khung cảnh.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1\le N\le50\,000\)) và \(K\) (\(1\le K\le10\)). Mỗi dòng trong \(N\) dòng còn lại chứa một trong các số nguyên \(x_1,\ldots,x_N\) (mỗi số nằm trong khoảng \(0\ldots1\,000\,000\,000\)).

Dữ liệu ra

In sức mạnh nhỏ nhất \(R\) cần dùng để phóng mỗi con bò nhằm làm nổ tất cả các kiện cỏ.

Ví dụ

7 2
20
25
18
8
10
3
1

5

Nguồn

USACO 2016 January Contest, Silver - Angry Cows: https://usaco.org/index.php?page=viewproblem2&cpid=594

Tác giả: Brian Dean.