CHALKIDIC ALPHABET

Euripus, the dolphin of Chalkida, after introducing the Chalkidic~^1~ alphabet to the central Mediterranean, decided to circulate scrolls using this specific alphabet in the numerous coastal cities of Evia. His job was to deliver letters to ~N~ ports located at coordinates (~X_i~, ~Y_i~). He starts his journey in the morning from his "home" at position (~0~, ~0~) and goes to his "office" at position (~A~, ~B~). In the afternoon, he returns to his home. Euripus can only deliver some of the letters as he goes to work and the rest as he returns. However, due to the tides of Chalkida, the first time he is forced to go only to points with a greater ~x~ than before, and when he returns, due to the change in the current, he is forced to go only to points with a smaller ~x~ than before.

~^1~ The Greek residents of Kyme (a region of Evia) transferred it to their colony, Kyme, which they founded in 754 BC in Lower Italy. From there, it spread throughout Italy. Their alphabet, during the Roman Empire, became established in the entire Western world as the Roman alphabet. The Chalkidic alphabet contained 7 letters of the now-called Latin alphabet: C, D, F (digamma), L, P, R, and S!!! Archaeological findings unequivocally confirm that the peculiar "Chalkidic" alphabet, where S was written as C, D as D, X as Χ, P as R, and Y as U, is the Latin (Etruscan) alphabet.

Problem.

Develop a program in one of the IOI languages that, after reading the data (port coordinates), will find the shortest distance that Euripus must travel to deliver all the letters. (An example route for Euripus is given in the diagram below:)

(Home: 0,0, Office: 15, 4, Port, Morning Route Afternoon Route)

Input Files

The input files with the name evripos.in are text files with the following structure: The first line contains a number ~N~ (~5 \le N \le 200~), the number of ports Euripus must visit. The second line, contains the coordinates ~A~, ~B~ of Euripus's "office." (~1 \le A, B \le 1.000~). In the next ~N~ lines, the coordinates ~X_i~, ~Y_i~ (\(1 \le Χ_i < A\) and ~-1000 \le Y_i \le 1.000~) of the ports to be visited are provided. All coordinate pairs are separated by a space.

Output Files

The output files with the name evripos.out are text files with the following structure: They have a single line containing a single number. The nearest integer, representing the minimum distance Euripus must travel to deliver all the letters.

Examples of Input - Output Files

1ο

STDIN (evripos.in)

10
15 4
3 4
4 0
5 4
6 0
7 4
8 0
9 4
10 0
11 4
12 0

STDOUT (evripos.out)

34

2ο

STDIN (evripos.in)

5
6 5
1 1
2 3
3 2
4 4
5 3

STDOUT (evripos.out)

16

Notes:

1. The distance between two points in two-dimensional space is calculated as ~d = ((X_2 - X_1)^2 + (Y_2 - Y_1)^2)^{1/2}~.
2. ~0 < X_i < A~,
3. All points have different ~X_i~ values.
4. There are at least three algorithmic solutions to the above problem with complexity O(~N~!), O(~2^N~), and O(~N^3~). Due to time constraints in solving the problem, the first solution will be scored with 50% of the total grade, the second with 70% - 80%, and the third with 100%, provided that they give correct results for the respective input files.
5. At the link http://hellenico.gr/evripos/, you will find a graphical environment for testing routes.