Camera an ninh

Khu dân cư Hùng Vương có \(n\) ngôi nhà đánh số từ \(1\) đến \(n\), các ngôi nhà được xây dựng trên một đường thẳng, nhà số \(i\) cách đầu khu dân cư một khoảng \(x_i\) (đơn vị độ dài). Ông trưởng khu dân cư có \(m\) camera an ninh và ông muốn mắc hết \(m\) camera này vào các nhà, mỗi nhà chỉ được mắc nhiều nhất \(1\) camera để đảm bảo an ninh trong khu dân cư.

Gọi \(d_i\) là khoảng cách từ ngôi nhà số \(i\) đến camera có khoảng cách gần nó nhất; nếu camera được mắc tại nhà \(i\) thì \(d_i = 0\).

Hãy tìm cách mắc camera sao cho \(S\) đạt giá trị nhỏ nhất với \(S = \max(d_i,\ 1 \le i \le n)\).

Input

Dữ liệu vào gồm:

• Dòng thứ nhất chứa hai số nguyên dương \(n, m\) (\(1 \le m < n\), \(2 \le n \le 10^5\));

• Dòng tiếp theo chứa \(n\) số nguyên dương \(x_i\) (\(x_i \le 10^{15}\), \(1 \le i \le n\)) là khoảng cách từ nhà \(i\) đến đầu khu dân cư. Dữ liệu vào đảm bảo \(x_1 < x_2 < \cdots < x_n\).

Ràng buộc:

• Có \(10\%\) số điểm của bài có \(m = n - 1\), \(x_i \le 10^7\);

• Có \(10\%\) số điểm của bài có \(m = 1\), \(x_i \le 10^7\);

• Có \(35\%\) số điểm của bài có \(n \le 100\), \(x_i \le 10^6\);

• Có \(45\%\) số điểm của bài có \(n \le 10^5\).

Output

In ra một số nguyên duy nhất là giá trị nhỏ nhất của \(S\).

Example

Input:

6 3
4 6 12 39 40 100

Output:

6

Note

Có nhiều cách mắc camera, chẳng hạn mắc vào các nhà số \(2, 4, 6\) (cách đầu khu lần lượt \(6, 39, 100\)). Khi đó \(d_1 = 2\) (nhà số \(1\) cách camera gần nhất đặt ở nhà số \(2\) là \(2\)), \(d_2 = 0\), \(d_3 = 6\), \(d_4 = 0\), \(d_5 = 1\), \(d_6 = 0\). Suy ra \(S = 6\), và đây là giá trị nhỏ nhất của \(S\) trong tất cả các cách mắc.