Problem: You are given two solid polygons and their positions on the xy-plane. You can move one of the two along the x-axis (they can overlap during the move). You cannot move it in other directions. The goal is to place them as compactly as possible, subject to the following condition: the distance between any point in one polygon and any point in the other must not be smaller than a given minimum distance L.

We define the width of a placement as the difference between the maximum and the minimum x-coordinates of all points in the two polygons.

Your job is to write a program to calculate the minimum width of placements satisfying the above condition.

Let's see an example. If the polygons in Figure 13 are placed with L = 10.0, the result will be 100. Figure 14 shows one of the optimal placements.

<image>



Input

The input consists of multiple datasets. Each dataset is given in the following format.


L
Polygon1
Polygon2


<image>

L is a decimal fraction, which means the required distance of two polygons. L is greater than 0.1 and less than 50.0.

The format of each polygon is as follows.


n
x1 y1
x2 y2
.
.
.
xn yn


n is a positive integer, which represents the number of vertices of the polygon. n is greater than 2 and less than 15.

Remaining lines represent the vertices of the polygon. A vertex data line has a pair of nonneg- ative integers which represent the x- and y-coordinates of a vertex. x- and y-coordinates are separated by a single space, and y-coordinate is immediately followed by a newline. x and y are less than 500.

Edges of the polygon connect vertices given in two adjacent vertex data lines, and vertices given in the last and the first vertex data lines. You may assume that the vertices are given in the counterclockwise order, and the contours of polygons are simple, i.e. they do not cross nor touch themselves.

Also, you may assume that the result is not sensitive to errors. In concrete terms, for a given pair of polygons, the minimum width is a function of the given minimum distance l. Let us denote the function w(l). Then you can assume that |w(L ± 10-7) - w(L)| < 10-4.

The end of the input is indicated by a line that only contains a zero. It is not a part of a dataset.

Output

The output should consist of a series of lines each containing a single decimal fraction. Each number should indicate the minimum width for the corresponding dataset. The answer should not have an error greater than 0.0001. You may output any number of digits after the decimal point, provided that the above accuracy condition is satisfied.

Example

Input

10.5235
3
0 0
100 100
0 100
4
0 50
20 50
20 80
0 80
10.0
4
120 45
140 35
140 65
120 55
8
0 0
100 0
100 100
0 100
0 55
80 90
80 10
0 45
10.0
3
0 0
1 0
0 1
3
0 100
1 101
0 101
10.0
3
0 0
1 0
0 100
3
0 50
100 50
0 51
0


Output

114.882476
100
1
110.5005

Solution (in CPP):

Solution:
#include <iostream>
#include <iomanip>
#include <complex>
#include <vector>
#include <algorithm>
#include <cmath>
#include <array>
using namespace std;
const double EPS = 1e-6;
const double INF = 1e12;
const double PI = acos(-1);
#define EQ(n,m) (abs((n)-(m)) < EPS)
#define X real()
#define Y imag()

typedef complex<double> P;
typedef vector<P> VP;
struct L : array<P, 2>{
    L(const P& a, const P& b){ at(0)=a; at(1)=b; }
    L(){}
};

namespace std{
    bool operator < (const P& a, const P& b){
        return !EQ(a.X,b.X) ? a.X<b.X : a.Y+EPS<b.Y;
    }
    bool operator == (const P& a, const P& b){
        return abs(a-b) < EPS;
    }
}

double dot(P a, P b){
    return (conj(a)*b).X;
}
double cross(P a, P b){
    return (conj(a)*b).Y;
}
int ccw(P a, P b, P c){
    b -= a;
    c -= a;
    if(cross(b,c) > EPS) return +1; //ccw
    if(cross(b,c) < -EPS) return -1; //cw
    if(dot(b,c) < -EPS) return +2; //c-a-b
    if(abs(c)-abs(b) > EPS) return -2; //a-b-c
    return 0; //a-c-b
}

bool intersectSS(const L& a, const L& b){
    return ( ccw(a[0],a[1],b[0]) *ccw(a[0],a[1],b[1]) <= 0 ) &&
        ( ccw(b[0],b[1],a[0]) *ccw(b[0],b[1],a[1]) <= 0 );
}
bool intersectSP(const L& s, const P &p){
    return abs(cross(s[0]-p, s[1]-p))<EPS  && dot(s[0]-p, s[1]-p)<EPS;
}

double distanceLP(const L &l, const P &p) {
    return abs(cross(l[1]-l[0], p-l[0])) /abs(l[1]-l[0]);
}
double distanceSP(const L &s, const P &p) {
    if(dot(s[1]-s[0], p-s[0]) < EPS) return abs(p-s[0]);
    if(dot(s[0]-s[1], p-s[1]) < EPS) return abs(p-s[1]);
    return distanceLP(s, p);
}
double distanceSS(const L &s, const L &t) {
  if (intersectSS(s, t)) return 0;
  return min(min(distanceSP(s, t[0]), distanceSP(s, t[1])),
             min(distanceSP(t, s[0]), distanceSP(t, s[1])));
}

bool isParallel(const P &a, const P &b){
    return abs(cross(a,b)) < EPS;
}
bool isParallel(const L &a, const L &b){
    return isParallel(a[1]-a[0], b[1]-b[0]);
}

P crosspointLL(const L &l, const L &m) {
  double A = cross(l[1]-l[0], m[1]-m[0]);
  double B = cross(l[1]-l[0], l[1]-m[0]);
  return m[0] + B/A *(m[1]-m[0]);
}

int in_poly(const P &p, const VP &poly){
    int n = poly.size();
    int ret = -1;
    for(int i=0; i<n; i++){
        P a = poly[i]-p;
        P b = poly[(i+1)%n]-p;
        if(a.Y > b.Y) swap(a,b);
        if(intersectSP(L(a,b), P(0,0))) return 0;
        if(a.Y<=0 && b.Y>0 && cross(a,b)<0) ret = -ret;
    }
    return ret;
}

double distanceGG(VP &a, VP &b){
    int n = a.size();
    int m = b.size();
    if(in_poly(a[0], b) > 0 || in_poly(b[0], a) > 0){
        return 0;
    }
    double ret = INF;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            ret = min(ret, distanceSS(L(a[i], a[(i+1)%n]), L(b[j], b[(j+1)%m])));
        }
    }
    return ret;
}

double leftend(VP &poly){
    double ret = INF;
    for(P p: poly){
        ret = min(ret, p.X);
    }
    return ret;
}
double rightend(VP &poly){
    double ret = -INF;
    for(P p: poly){
        ret = max(ret, p.X);
    }
    return ret;
}
VP slide(VP poly, double d){
    for(P &p: poly){
        p += P(d, 0);
    }
    return poly;
}
L slide(L l, double d){
    return L(l[0] +P(d, 0), l[1] +P(d, 0));
}
//aとbの距離を最も近づけるためには, bをx方向にretスライドすればよい
double closest_slide(L a, L b){
    if(a[0].Y > a[1].Y) swap(a[0], a[1]);
    if(b[0].Y > b[1].Y) swap(b[0], b[1]);
    //Yの範囲に被りがある
    for(int d=0; d<2; d++){
        for(int i=0; i<2; i++){
            if(b[0].Y +EPS < a[i].Y && a[i].Y +EPS < b[1].Y){
                L hori(a[i], a[i] +P(1, 0));
                P cp = crosspointLL(hori, b);
                double diff = a[i].X -cp.X;
                return (d == 0)? diff : -diff;
            }
        }
        swap(a, b);
    }
    //ない
    if(a[1].Y < b[0].Y +EPS){
        return a[1].X -b[0].X;
    }else{
        return a[0].X -b[1].X;
    }
}

int main(){
    cout << fixed << setprecision(5);
    while(1){
        double d;
        cin >> d;
        if(d == 0) break;

        vector<VP> poly(2);
        for(int d=0; d<2; d++){
            int n;
            cin >> n;
            poly[d].resize(n);
            for(int i=0; i<n; i++){
                double x,y;
                cin >> x >> y;
                poly[d][i] = P(x, y);
            }
        }
        double diff = leftend(poly[1]) -leftend(poly[0]);
        poly[1] = slide(poly[1], -diff);
        if(distanceGG(poly[0], poly[1]) +EPS > d){
            double left = min(leftend(poly[0]), leftend(poly[1]));
            double right = max(rightend(poly[0]), rightend(poly[1]));
            cout << right -left << endl;
            continue;
        }

        int n = poly[0].size();
        int m = poly[1].size();
        vector<double> cand;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                L edge[2];
                edge[0] = L(poly[0][i], poly[0][(i+1)%n]);
                edge[1] = L(poly[1][j], poly[1][(j+1)%m]);
                double csd = closest_slide(edge[0], edge[1]);
                edge[1] = slide(edge[1], csd);
                //NG範囲をもたない
                if(distanceSS(edge[0], edge[1]) +EPS > d){
                    continue;
                }
                //NG範囲をにぶたん
                for(int s=0; s<2; s++){
                    double lb=0, ub=1e4;
                    for(int rep=0; rep<50; rep++){
                        double mid = (lb +ub) /2;
                        L tmp = (s==0)? slide(edge[1], mid) : slide(edge[1], -mid);
                        if(distanceSS(edge[0], tmp) > d){
                            ub = mid;
                        }else{
                            lb = mid;
                        }
                    }
                    if(s == 0){
                        cand.push_back(csd +lb);
                    }else{
                        cand.push_back(csd -lb);
                    }
                }
            }
        }

        double ans = INF;
        for(double dist: cand){
            VP tmp = slide(poly[1], dist);
            if(distanceGG(poly[0], tmp) +EPS > d){
                double left = min(leftend(poly[0]), leftend(tmp));
                double right = max(rightend(poly[0]), rightend(tmp));
                ans = min(ans, right -left);
            }
        }
        cout << ans << endl;
    }
    return 0;
}