F - Falconry Editorial /

Time Limit: 8 sec / Memory Limit: 512 MB

Problem

Falconry is a kind of hunting using a bird of prey. One day, three falconers (the person who do falconry) decided to carry out the next competition.

There are N checkpoints on a two-dimensional plane, the i_{th} checkpoint exists on the point of which the coordinate is (x_i,y_i). The three falconers exist on the points of which the coordinates are (x_a, y_a), (x_b, y_b), (x_c, y_c). Each one of them has one bird. In the beginning, every bird stays with its owner, thus the coordinate of it is the same as that of its owner.

When the competition begins, 3 birds will start to move. The purpose of this competition is to let all the checkpoints to be passed through by one bird at least, and to minimize the sum of the moving distance of the three birds. In this case, distance refers to the Euclidean Distance. The distance between two points (x_s, y_s) and (x_t, y_t) is \sqrt{(x_s - x_t)^2 + (y_s - y_t)^2}.

Checkpoints can be passed through in any order. For a bird, it is allowed to pass no checkpoint or pass all the checkpoints. Also, the same checkpoint can be passed through more than once. In addition, suppose that each bird can choose the optimal way to move.

The coordinates of all the checkpoints and the three falconers will be given. Please find the minimum value of the sum of the moving distance of three birds.

Input

Inputs will be given by standard input in following format

N
x_1 y_1
x_2 y_2
:
x_N y_N
x_a y_a
x_b y_b
x_c y_c
  • For the first line, N (1 ≦ N ≦ 18) will be given.
  • From the second line, there are N additional lines, for each line the coordinate of a checkpoint will be given. For the i_{th} line, integer x_i(-10,000≦x_i≦10,000), y_i(-10,000≦y_i≦10,000) will be given divided by a space.
  • For the (N+2)_{th} line, x_a(-10,000≦x_a≦10,000)、y_a(-10,000≦y_a≦10,000) will be given divided by a space.
  • For the (N+3)_{th} line, x_b(-10,000≦x_b≦10,000)、y_b(-10,000≦y_b≦10,000) will be given divided by a space.
  • For the (N+4)_{th} line x_c(-10,000≦x_c≦10,000)、y_c(-10,000≦y_c≦10,000) will be given divided by a space.

In addition, all the coordinates are different from each other.

In other words, if i \neq j then (x_i, y_i) \neq (x_j, y_j).

Also, for each i (1 ≦ i ≦ N), (x_i, y_i) \neq (x_a, y_a), (x_i, y_i) \neq (x_b, y_b) and (x_i, y_i) \neq (x_c, y_c) will hold. Furthermore, (x_a, y_a) \neq (x_b, y_b), (x_b, y_b) \neq (x_c, y_c) and (x_c, y_c) \neq (x_a, y_a) will hold.

Output

Output the minimum value of the sum of the moving distance of three birds when all the checkpoints have been passed through by at least one bird in one line.

The output is acceptable if absolute error or relative error is 10^{-6} or less.

Print a newline at the end of output.

Input Example 1

3
1 1
102 98
197 -197
0 0
100 100
200 -200

Output Example 1

8.485281374239
  • If the bird that starts from (x_a, y_a) passes through the first checkpoint, the moving distance will be \sqrt{2}.
  • If the bird that starts from (x_b, y_b) passes through the second checkpoint, the moving distance will be 2\sqrt{2}.
  • If the bird that starts from (x_c, y_c) passes through the third checkpoint, the moving distance will be 3\sqrt{2}.

Hence, by moving 6\sqrt{2}all the checkpoints will be passed through at least once.

Input Example 2

3
1 3
2 1
0 -2
0 0
-500 0
0 1000

Output Example 2

7.841619252964

If the bird that starts from (x_a, y_a) passes the third checkpoint, then passes the second checkpoint, then passes the first checkpoint, the moving distance in total will be 2 + \sqrt{13} + \sqrt{5}.

Input Example 3

6
3 7
1 10
-2 -5
-3 4
0 2
6 6
-3 9
0 4
1 1

Output Example 3

22.585258012904