Problem: Monkey Tour

Want to try solving this problem? You can submit your code online if you log in or register.

Monkey Tour

Time Limit: 0.2 seconds
Memory Limit: 64 Mb

Trevor the monkey has been placed into an artificial animal reserve. It's rather obvious that the forest is not natural: all of the trees have been planted in a perfect grid formation, with each tree separated by 1 metre from its neighbour! Trees in this forest are so close to each other that no large branches can grow, and as a consequence Trevor has no peaceful place to rest. He solves this problem by building a certain number of nests, N, inside some of the trees.

The management of the reserve have defined Trevor's territory to be a square area of side S metres located well inside the reserve. All of Trevor's nests lie within this square or on its boundary. Trevor is allowed to move outside his territory, but the reserve is so large that even if he does this there is no way he can reach the border.

Since all the branches are very small, it is quite hazardous for a big monkey like Trevor to climb from tree to tree. Because of this, Trevor will only move from tree to tree by swinging on vines, as Tarzan used to teach him when he was young. Vines can always be found wherever they are neeeded in this forest, and so this method of transport is quick and efficient. There are however some restrictions:

To swing between two trees, there cannot be any other tree on a straight line between them (otherwise, smashed monkey).
Vines are only long enough to travel a distance L or less in a single swing.

Swinging on vines is quite exhausting, even for a trained monkey, and so Trevor would like to minimise his fatigue as he travels between his nests. To move between two nests, he uses vines to swing from tree to tree, possibly having little rests at other nests along the way. Since these rests are quite refreshing, Trevor does not measure his fatigue by the total number of swings. Instead he measures his fatigue by the largest number of consecutive swings taken without any rests in between.

Trevor is quite lazy and not that clever — he is a real monkey. He'd like you to help him find a group of at least N/2 nests that he can travel between, so that the greatest fatigue that he must endure between any of these N/2 nests is as small as possible. If N is odd then N/2 should be rounded up to the integer above.

Constraints

1 <= L <= 15, where L is the maximum distance for a single swing;
2 <= S <= 200, where S is the side length of Trevor's territory;
2 <= N <= 1000, where N is the number of nests that Trevor has built;
0 <= Xi < S and 0 <= Yi < S, where (Xi, Yi) are the co-ordinates of the ith nest.

Furthermore, for 30% of the available marks you are guaranteed that L <= 3, S <= 100 and N <= 65.

Input

The first line of input will contain the single integer L, giving the maximum distance that can be travelled in a single swing (measured in metres). The second line of input will contain the single integer S, giving the side length of the square territory (again measured in metres). The third line of input will contain the single integer N, giving the total number of nests.

Following this will be N lines, each containing two integers Xi and Yi separated by a space, giving the x-coordinate and y-coordinate of each nest. No two nests will occupy the same location.

Output

Output should consist of a single line containing a single integer: the minimum fatigue that Trevor must endure in order to be able to travel anywhere within some group of at least N/2 nests.

Sample Input

The input scenario above describes the forest in the illustration below. Trees are marked with black circles, and the five nests are marked with the letters A, B, C, D and E. Note that in this example we can swing a maximum distance of L = 3 metres.

Consider nests A and B. Although these are three metres away, Trevor cannot swing directly between them since there are other trees in the way. He therefore needs at least two swings. For example, he could swing from A=(0,0) to (-1,2) and from there to B=(0,3). This route is marked with a solid line on the map. Note that this route goes outside Trevor's territory (which is perfectly allowable).

To travel between nests A and E, Trevor needs at least three swings; again he cannot take a more direct route since there are other trees in the way. One possible route from A to E might be from A=(0,0) to (1,2), then to (2,3) and finally to E=(1,5).

Note however that Trevor can travel from A to E with a fatigue of only 2. He does this by travelling from A to B with two swings, then resting in nest B, and finally travelling on from B to E with one additional swing. Since at most two consecutive swings are taken without a rest between them, the total fatigue for this new journey from A to E is 2.

Sample Output

Recall that Trevor is seeking a group of three nests (N/2 rounded up) that he can travel between. If he chooses nests A, B and E, we see that he can reach any nest from any other nest within this group with a fatigue of at most 2. There is no other group of three nests that gives a better result (though there are many others that give the same result), and so 2 is the final answer.

Scoring

The score for each input scenario will be 100% if the correct answer is output, and 0% otherwise.