Kitchen Robot#2268
Robots are becoming increasingly popular over time. Today, they are used not only in large factories, but also in everyday household settings. One programmer, together with his friends, decided to create their own home robot. As you may know, many programmers enjoy getting together at parties and drinking beer. After such parties, the table is usually left covered with empty bottles. Therefore, they decided to develop a robot capable of collecting empty bottles from the table.
The table is a rectangle of length and width . The robot starts at the point (x_r, y_r), and bottles are located at the points (x_i, y_i), where 1 \le i \le n. To pick up a bottle, the robot must move to its location, grab it, and then carry it to some point on the boundary of the table and release it. At any moment, the robot can hold only one bottle, and it may release it only at the boundary of the table.
The sizes of the bottles and the robot can be considered negligible (both the robot and the bottles are points). A robot holding a bottle may pass through points where other bottles are located.
One of the robot’s subprograms is route planning. You are required to write a program that determines the shortest possible route by which the robot can collect all the bottles.
The first line contains two integers and l~(2 \le w, l \le 1000) — the width and length of the table.
The second line contains the number of bottles n~(1 \le n \le 18). Each of the next lines contains two integers x_i and y_i~(0 < x_i < w,\ 0 < y_i < l) — the coordinates of the -th bottle. No two bottles are located at the same point.
The last line contains two integers x_r and y_r~(0 < x_r < w, 0 < y_r < l) — the coordinates of the robot's starting position. The robot is not located at the same point as any bottle.
Print the length of the shortest route by which the robot collects all bottles. The computation error must not exceed 10^{-6}.
Example 1