Trip abroad

Time limit = 5 second(s)

Memory limit = 33000 Kb

But he has no much time and he desided to choose the shortest path.

Petya has found that train roads are only between towns which stay away no more than distance R.

Please, help him to do it. Positions of all neibor towns are given and there is regular train transport between each two towns. The border is the line x=0.

Input Line 1: N — number of towns. 3 ≤ N ≤ 300.
Line 2: R — real number, maximal length of a road 0 ≤ R ≤ 300.
Line 3: Coordinates of A.
Line 4: Coordinates of B.
Line 5..N+2: Coordinates of other towns.
All coordinates are real numbers from the interval (-100 000, 100000). Coordinate X (the first one) of the towns A and B is positive. There is no towns laying at the border x=0.

At least one way from A to B satisfying above conditions exists.

Output Minimal distance. Error should be less than 0.01.

4
4.5
1 -1
1 1
-1 -1
-1 1

4.828

Author:

23 september 2003

<PREV | Problem set | Search related messages | NEXT>