At Bolonel Cy Secondary School, student desks are fixed onto the ground! In particular, there are \(N\) desks, with the \(i\)-th desk being \(N_i\) centimetres away from the left wall of the classroom. There are \(M\) students who will each need to be seated into a particular desk. In order to respect social distancing, the principal wishes to arrange the seating plan such that students are seated as far away as possible from each other (numerically, we want to maximize the minimum difference between adjacent students). Note that there will always be enough desks for everybody, and there will always be at least two students.

Please help the principal determine the maximum social distance between all seated students!

Input Specification

The first line of the input will contain two integers \(N\) and \(M\) \((2 \le N \le M \le 10^5)\), indicating the number of desks and the number of students respectively.

The next line of the input will contain \(N\) integers \(N_i\) \((0 \le N_{i-1} \le N_i \le 10^9)\). The \(i\)-th integer indicates the distance between the \(i\)-th location and the left wall.

Output Specification

Output an integer, representing the maximized minimum distance between seated students.

Subtasks

Subtask 1 [50%]

\(2 \le N \le M \le 50\)

Subtask 2 [50%]

No additional constraints.

Sample Input

5 3
1 3 4 7 11

Sample Output

4

Sample Explanation

By seating the students at position \(1\), \(7\), and \(11\), the maximized minimum difference of \(\mathcal{min}(7 - 1, 11 - 7)\) is \(4\). There are no better combinations than this one.