Minimize Highway Emptiness Index

The government has decided to add some road signs on a highway to minimize its "emptiness index." The highway is of integer length L and already has road signs at the starting point (0) and the ending point (L). There may also be some additional road signs already installed at some integer positions between 0 and L. You are allowed to add at most M new road signs at integer positions along the highway. The emptiness index is defined as the maximum distance between any two consecutive road signs.

Your task is to compute the minimum possible emptiness index achievable by optimally adding new road signs.

The formula to compute the number of extra signs required to cover a gap of length g when the maximum allowed gap is d is given by:

[ \text{required} = \left\lfloor \frac{g-1}{d} \right\rfloor ]

You need to find the minimum d such that the total extra signs required for all gaps does not exceed M.

inputFormat

The input consists of two lines. The first line contains three space-separated integers:

• L: the length of the highway.
• N: the number of existing road signs (including the mandatory ones at positions 0 and L).
• M: the maximum number of new road signs you can add.

The second line contains N space-separated integers representing the positions of the existing road signs. All positions are integers, and the positions are not necessarily given in order.

outputFormat

Output a single integer representing the minimized emptiness index (i.e. the minimum possible maximum gap between consecutive road signs after adding at most M new signs).

sample

100 2 1
0 100

50