Hide

Problem C
Hiding Chickens

“Weeeee,” says the fox after breaking in to the roost and killing all the chickens. Then he realizes that he has killed way more chickens then he can eat right now and hence he decides to hide them in already existing hiding spots nearby. The fox can only carry two hens at a time and every hiding spot can fit at most one. As he is already tired after all the killing, he wants you to compute the minimum distance he has to walk to hide all of the dead chickens.

Input

The first line of input gives the position of the roost as two real numbers $x$ and $y$ on a single line. The next line contains an integer $1 \leq N \leq 20$, giving the number of hiding spots and dead chickens. Then follow $N$ lines, each line consisting of two real numbers giving the coordinates of a hiding spot. All coordinate values are between $0$ and $1\, 000$ and given with $6$-digit precision.

Output

A single line with a floating point number, the minimum distance the fox has to walk to hide all the chickens. Any answer with an error of at most $10^{-6}$ will be judged as correct.

Sample Input 1 Sample Output 1
10.000000 20.123456
1
13.141593 20.123456
3.141593
Sample Input 2 Sample Output 2
5.000000 5.000000
4
2.000000 9.000000
14.000000 17.000000
6.500000 3.000000
14.000000 18.500000
31.500000

Please log in to submit a solution to this problem

Log in