Shy Polygon

You are given two solid polygons together with their positions on the $xy$-plane. You may slide one of the two polygons along the $x$-axis; the two polygons are allowed to overlap while it is being moved. You may not translate it in any other direction, and you may not rotate it.

Place the two polygons as compactly as possible while satisfying this condition: the distance between every point of one polygon and every point of the other polygon must be at least a given value $L$. Because the polygons are solid, a "point of a polygon" may lie on its boundary or in its interior; in particular, if the two polygons overlap, the distance between them is $0$.

The width of a placement is the difference between the largest and the smallest $x$-coordinate taken over all points of the two polygons. Write a program that computes the minimum possible width over all placements that satisfy the condition above.

For example, if the two polygons in Figure 13 are placed with $L = 10.0$, the minimum width is $100$. Figure 14 shows one such optimal placement.

Figure 13: Initial positions of the two polygons

Figure 14: One optimal placement ($L = 10.0$)

The input consists of several datasets. Each dataset has the following format:

L
Polygon1
Polygon2

$L$ is a decimal number, the required minimum distance between the two polygons, with $0.1 < L < 50.0$.

Each polygon is given as:

n
x1 y1
x2 y2
...
xn yn

$n$ is the number of vertices of the polygon, with $2 < n < 15$. Each of the next $n$ lines contains two nonnegative integers, the $x$- and $y$-coordinates of a vertex separated by a single space; both coordinates are less than $500$.

Edges connect consecutive vertices, and also the last vertex back to the first. The vertices are listed in counterclockwise order, and every polygon is simple: its boundary neither crosses nor touches itself.

You may assume the result is numerically stable. For a fixed pair of polygons, let $w(l)$ denote the minimum width as a function of the required distance $l$; then $|w(L \pm 10^{-7}) - w(L)| < 10^{-4}$.

The end of the input is a line containing a single $0$; it is not part of any dataset.

For each dataset, print one line containing the minimum width, rounded to exactly six digits after the decimal point.