16004번 - 헬리콥터 스페셜 저지

프로도는 헬리콥터 조종 면허를 따기 위해 연습 중이다. 헬리콥터 조종 면허의 실기 시험은 2차원 XY 직교 좌표계의 수평 길이가 L 인 코스에서 치러진다. 헬리콥터는 해당 코스의 왼쪽 수평 끝 (0, 0)에서 이륙하여 오른쪽 수평 끝 (L, 0)에 착륙해야 한다. 이때 각각의 X 좌표마다 헬리콥터가 날 수 있는 비행 높이 Y 가 범위로 정해져 있는데, 실기 시험에 합격하기 위해서는 이 범위를 지키며 주어진 코스를 가능한 짧은 비행거리로 날아야 한다.

헬리콥터는 언제나 X 좌표가 증가하는 방향, 즉 왼쪽에서 오른쪽으로 이동하며 해당 X 좌표의 비행 범위 내에서 Y 좌표를 위아래로 이동할 수 있다. 단, 안전을 위해 규칙상 X 좌표와 Y 좌표를 동시에 움직여서는 안 된다. 즉 헬리콥터는 한 번에 수평 혹은 수직 방향으로만 움직여야 한다. 하지만 프로도는 딱 한 번, 면접관의 눈을 속여 X, Y 좌표가 함께 변하는 대각선 비행이 가능하다. 아래 그림은 실기 시험 코스와 그 코스에 따라 프로도가 비행할 수 있는 경로의 한 예이다.

비행거리란 헬리콥터가 나는 비행경로 선분 길이의 총합이다. 위 그림의 경로는 프로도의 헬리콥터가 날 수 있는 가장 짧은 비행거리가 아닐 수도 있다. 하늘을 날고 싶은 프로도를 위해, 조건을 만족하며 프로도의 헬리콥터가 날 수 있는 가장 짧은 비행거리를 구해주자.

첫 번째 줄에 코스의 수평 길이 L, 비행 범위 위쪽 경계에 포함된 꼭짓점의 개수 N, 비행 범위 아래쪽 경계에 포함된 꼭짓점의 개수 M 이 주어진다. (2≤ N, M ≤300)

다음 N 개의 줄에는 각각 차례로 위쪽 경계의 가장 왼쪽 꼭짓점부터 오른쪽으로 위쪽 경계에 포함되는 꼭짓점들의 x, y 좌표가 주어진다.

다음 M 개의 줄에는 마찬가지로 아래쪽 경계의 가장 왼쪽 꼭짓점부터 오른쪽으로 아래쪽 경계에 포함되는 꼭짓점들의 x, y 좌표가 주어진다.

N 과 M 은 항상 짝수로 주어지며, 이로 인해 만들어지는 코스는 위아래로 홀수개의 수직/수평 선분으로 이루어진 직각 다각형의 형태이다. 각 경계의 처음과 마지막 선분은 수평 방향이며, 수평 선분 다음에는 수직 선분으로, 수직 선분 다음에는 수평 선분으로 구성된다. 위쪽 경계와 아래쪽 경계는 만나지 않는다.

각 경계의 첫 꼭짓점의 X 좌표는 항상 0이며, 마지막 꼭짓점의 X 좌표는 항상 L 이다. 또한 아래쪽 경계의 첫 꼭짓점과 마지막 꼭짓점의 Y 좌표는 항상 0이다.

주어지는 모든 입력은 0 이상 10⁹ 이하의 정수이다. 헬리콥터는 Y 좌표 0에서도 비행이 가능하며, 비행이 불가능한 코스는 주어지지 않는다.

프로도의 헬리콥터가 조건을 만족하며 날 수 있는 비행거리 중 가장 짧은 것의 길이를 출력한다. 출력한 결과와 실제 답을 비교하였을 때의 상대 혹은 절대 오차가 10^-6 이하인 경우에만 정답으로 인정한다.