Задача B. Мост ≡

Автор:	Жюри ВКОШП-2008		Ограничение времени:	2 сек
Входной файл:	bridge.in		Ограничение памяти:	256 Мб
Выходной файл:	bridge.out

Условие

Власти Флатландии решили построить новый мост через реку Нижний Флат, протекающую с юга на север через территорию страны. В связи с финансовым кризисом средства строителей существенно ограничены, поэтому решено было построить мост минимальной возможной длины.

Введем координатную систему таким образом, чтобы ось OY была направлена с юга на север, а ось OX — с запада на восток. Берега реки представляют собой ломаные, бесконечные в обе стороны. Левый берег начинается лучом, направленным на юг из точки (x_1,1; y1,1), продолжается отрезками (x_1,1 y_1,1) − (x_1,2; y_1,2), (x_1,2; y_1,2) − (x_1,3; y_1,3), … , (x_1,m−1; y_1,m−1) − (x_1,m; y_1,m) и заканчивается лучом, направленным на север из точки (x_1,m; y_1,m). Аналогично, правый берег реки начинается лучом, направленным на юг из точки (x_2,1; y_2,1), продолжается отрезками (x_2,1; y_2,1) − (x_2,2; y_2,2), (x_2,2; y_2,2) − (x_2,3; y_2,3), … , (x_2,n−1; y_2,n−1) − (x_2,n; y_2,n) и заканчивается лучом, направленным на север из точки (x_2,n; y_2,n).

Помогите руководству Флатландии выяснить, мост какой минимальной длины можно построить. Оптимальное положение моста для приведенного ниже примера показано на рисунке.

Формат входного файла

Первая строка входного файла содержит целое число m. Следующие m строк содержат по два целых числа — координаты вершин ломаной левого берега: x_1,1, y_1,1, x_1,2, y_1,2, … , x_1,m, y_1,m.

Следующая строка входного файла содержит целое число n. Следующие n строк содержат по два целых числа — координаты вершин ломаной левого берега: x_2,1, y_2,1, x_2,2, y_2,2, … , x_2,m, y_2,m.

Известно, что x_1,1 < x_2,1, каждая из ломаных не имеет самопересечений и самокасаний, ломаные не имеют общих точек. Все отрезки каждой из ломаных имеют положительную длину. Все координаты не превосходят 10⁴ по абсолютной величине.

Формат выходного файла

Выведите в выходной файл одно вещественное число: минимальную возможную длину моста. Ваш ответ будет проверяться с точностью 10⁻⁵.

Ограничения

2 ≤ m,n ≤ 100

Примеры тестов

№	Входной файл (bridge.in)	Выходной файл (bridge.out)
1	4 6 1 3 1 3 0 0 3 3 9 3 2 3 6 5 скопировать	1.41421356237309505 скопировать

---