수줍은 다각형

$xy$ 평면 위에 놓인, 속이 꽉 찬 두 개의 다각형과 그 위치가 주어진다. 두 다각형 중 하나를 $x$축 방향으로만 평행이동할 수 있으며, 이동하는 도중에는 두 다각형이 서로 겹쳐도 된다. 다른 방향으로 옮기거나 회전시킬 수는 없다.

다음 조건을 지키면서 두 다각형을 최대한 촘촘하게 배치하려고 한다: 한 다각형 위의 임의의 점과 다른 다각형 위의 임의의 점 사이의 거리가 항상 주어진 값 $L$ 이상이어야 한다. 다각형은 속이 꽉 차 있으므로 "다각형 위의 점"은 경계뿐 아니라 내부의 점도 포함한다. 특히 두 다각형이 겹치면 둘 사이의 거리는 $0$이다.

어떤 배치의 너비는 두 다각형에 속한 모든 점의 $x$좌표 가운데 최댓값과 최솟값의 차이다. 위 조건을 만족하는 모든 배치 중 가능한 최소 너비를 구하는 프로그램을 작성하라.

예를 들어 그림 13의 두 다각형을 $L = 10.0$으로 배치하면 최소 너비는 $100$이다. 그림 14는 그러한 최적 배치의 한 예이다.

그림 13: 두 다각형의 처음 위치

그림 14: 최적 배치의 한 예 ($L = 10.0$)

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋의 형식은 다음과 같다.

L
다각형1
다각형2

$L$은 두 다각형이 유지해야 하는 최소 거리를 나타내는 실수이며 $0.1 < L < 50.0$이다.

각 다각형은 다음 형식으로 주어진다.

n
x1 y1
x2 y2
...
xn yn

$n$은 다각형의 꼭짓점 개수로 $2 < n < 15$이다. 이어지는 $n$개의 줄에는 각 꼭짓점의 $x$, $y$ 좌표가 공백 하나로 구분되어 주어지며, 두 좌표 모두 음이 아닌 정수이고 $500$보다 작다.

다각형의 변은 인접한 두 꼭짓점을 잇고, 마지막 꼭짓점과 첫 번째 꼭짓점도 잇는다. 꼭짓점은 반시계 방향으로 주어지며, 모든 다각형은 단순하다(경계가 스스로 교차하거나 맞닿지 않는다).

답은 수치적으로 안정적이라고 가정해도 된다. 고정된 두 다각형에 대해 요구 거리 $l$의 함수로서 최소 너비를 $w(l)$이라 하면 $|w(L \pm 10^{-7}) - w(L)| < 10^{-4}$이다.

입력의 끝은 $0$ 하나만 있는 줄로 나타내며, 이 줄은 어떤 데이터셋에도 속하지 않는다.

각 데이터셋에 대해 최소 너비를 소수점 아래 정확히 여섯 자리로 반올림하여 한 줄에 출력한다.