Standing Long Jump

Students train for the standing long jump. The training ground is filled with boiling lava, so a student must cross to the exit on the far side by stepping on stone islands placed over the lava.

The student starts on the island at position $0$, and the exit is at position $d$. Between the start island and the exit there are $n$ small stone islands; the position of each island is given as its distance from the start island.

The teacher removes exactly $m$ of these $n$ small islands. The student then steps on every one of the remaining $n-m$ small islands, jumping in order of position from the start island to the exit. (No matter how far apart two islands are, the jump always succeeds — the student never falls into the lava.)

The length of a single jump is the distance between two consecutive stepping points. That is, lay out the start island, the remaining small islands, and the exit in order of position; the distances between adjacent points are the jump lengths.

Choose which $m$ islands to remove so as to maximize the minimum jump length. Output that maximum possible value.

The first line contains the distance $d$ from the start island to the exit ($1 \le d \le 10^9$), the number of small islands $n$ ($0 \le n \le 50000$), and the number of islands to remove $m$ ($0 \le m \le n$), separated by spaces.

Each of the next $n$ lines contains one integer: the position of a small island (its distance from the start island). All island positions are distinct.

Print the maximum achievable value of the minimum jump length after removing $m$ islands.