407763: GYM102890 N Network connection

A new road connecting Nlogonia and Quadradonia was built, the road is a straight line of $$$D$$$ meters long. Nlogonia is at meter $$$0$$$ in the road, and Quadradonia is at meter $$$D$$$ in the road. One of the advantages of this road is it offers free internet access to anyone that travels it using public transportation system, this encourages people to travel between the cities without using their vehicles reducing in this way carbon emissions between the cities.

To provide internet access in all the road $$$M$$$ internet antennas have been installed along the road. Two antennas in the road can pass internet signal between them if and only if the distance between them is less or equal than a configured frequency range. In the same way an antenna is connected to a city internet network if the distance from the antenna to the city is less or equal to the antenna range. The frequency range of the antennas can be configured to any positive integer, but, in order for the antennas to work properly, this value should be the same for all the antennas in the road.

People that travels using public transportation in the road have filled several complains stating they do not have internet access in all the road, so, the public transportation officers of the cities have asked you to investigate further and fix the problem.

You need to review the current installation of the internet antennas, your task is to find the minimum range that should be configured to the antennas to make sure that there is a connection between Nlogonia and Quadradonia. For such connection to exists, there should be a set of antennas in such way that at least one antenna is connected to Nlogonia internet network, at least one antenna is connected to Quadradonia internet network, and for every other antenna there is a way to pass internet signal to both cities, following a set of antennas with the configured frequency range. To help you in this mission the public transportation officers will assign a budget $$$B$$$, and they will allow you to move the antennas from their current position, but you can not install more antennas, moving an antenna $$$m$$$ meters from it's initial position will cost you $$$m$$$ from the given budget.

Given the current position of the $$$M$$$ antennas, the budget $$$B$$$ assigned, and the distance $$$D$$$ of the road, write a program that finds the minimum range frequency that can be configured to the antennas to connect internet in all the road without exceeding the budget $$$B$$$.

The first line of input contains three integers separated by a space, $$$D$$$, $$$B$$$, and $$$M$$$ ($$$1 \leq D \leq 5000$$$, $$$0 \leq B \leq 10^6$$$, $$$1 \leq M \leq 100$$$), representing respectively, the distance of the road, the maximum budget you can spend, and the number of installed antennas in the road.The second and last line of input contains $$$M$$$ integer numbers separated by a space, the values $$$p_i$$$ ($$$0 \leq p_i \leq D$$$), representing the $$$i$$$-th antenna is positioned at meter $$$p_i$$$ in the road.

Output a line containing a single integer, the minimum range frequency that can be configured to the antennas to connect internet in all the road without exceeding the budget.

10 0 2
0 10

10

10 5 2
0 10

5

10 5 2
0 0

5