Optimal Courier Delivery Route

Since 2010, the online shopping market has grown rapidly, and courier companies have become a key link in ensuring successful transactions. In this problem, you are given two parallel streets with a vertical separation of \(d\). There are two courier workstations located on these two streets: \(S_1\) is on street A at x-coordinate \(s_1\) and \(S_2\) is on street B at x-coordinate \(s_2\). Additionally, there are several delivery points on these two streets. Each point on street A (resp. street B) is specified by its x-coordinate.

The courier starts at workstation \(S_1\) on street A, must deliver packages to all delivery points (in any order), and then finish at workstation \(S_2\) on street B. The distance between two points on the same street is the absolute difference of their x-coordinates. When moving between points on different streets, the distance is measured by the Euclidean distance, that is, for two points with x-coordinates \(x_1\) and \(x_2\) located on different streets, the distance is \(\sqrt{(x_1-x_2)^2+d^2}\).

Your task is to compute the length of the shortest route that starts at \(S_1\), visits all the delivery points, and ends at \(S_2\).

Note: You may assume that the positions on each street are given in arbitrary order and that the optimal visiting order is not necessarily the sorted order. However, due to the special structure (all points lie on two parallel lines), a dynamic programming solution based on sorting the points can be used to determine the minimum route length.

Example:

Let \(d=2\). Suppose \(S_1\) is on street A at \(x=1\) and \(S_2\) is on street B at \(x=3\). There are two delivery points: one on street A at \(x=3\) and one on street B at \(x=1\). One optimal route is:

• Start at \(S_1\) at \(x=1\) (street A)
• Deliver on street A at \(x=3\) (distance = \(|3-1|=2\))
• Cross to street B to deliver at \(x=1\) (distance = \(\sqrt{(3-1)^2+2^2}=\sqrt{8}\approx2.828427\))
• Finally, go from \(x=1\) on street B to \(S_2\) at \(x=3\) (distance = \(|3-1|=2\))

The total distance is approximately \(6.828427\).

inputFormat

The input consists of several lines:

1. The first line contains a single integer \(d\) \( (1 \leq d \leq 10^4)\), representing the vertical distance between the two parallel streets.
2. The second line contains two integers \(s_1\) and \(s_2\) \( (0 \leq s_1, s_2 \leq 10^4)\): the x-coordinates of workstation \(S_1\) on street A and workstation \(S_2\) on street B respectively.
3. The third line contains a non-negative integer \(n\) (number of delivery points on street A).
4. If \(n > 0\), the fourth line contains \(n\) integers representing the x-coordinates of the delivery points on street A.
5. The next line contains a non-negative integer \(m\) (number of delivery points on street B).
6. If \(m > 0\), the following line contains \(m\) integers representing the x-coordinates of the delivery points on street B.

Note that the delivery point coordinates may be in arbitrary order.

outputFormat

Output a single number: the length of the shortest route. The result must be printed with at least 6 decimal places of precision.

sample

2
1 3
1
3
1
1

6.828427