야경 (Nightman)

넓은 부지의 Y 센터는 국영 복합 연수 시설로, 동아리 모임과 합숙, 시민 악단의 정기 연주회, 기업 신입 사원 연수 등 다양한 목적으로 많은 사람이 이용한다.

아래 그림처럼 Y 센터의 부지는 가로 $w$ × 세로 $h$인 직사각형이다. 왼쪽 아래 좌표가 $(0, 0)$, 오른쪽 위 좌표가 $(w, h)$이다.

그림 1: 가로 8, 세로 6인 Y 센터 ($w = 8$, $h = 6$인 경우)

Y 센터에는 $b$개의 건물이 있다. 건물은 모두 직사각형이고 각 변은 좌표축 중 하나와 평행하다. 건물의 위치는 네 정수 $(s_i, t_i, u_i, v_i)$ ($i = 1, \dots, b$)로 나타낸다. $i$번째 건물의 왼쪽 아래 좌표가 $(s_i, t_i)$, 오른쪽 위 좌표가 $(u_i, v_i)$이며, 변 위는 건물 영역에 포함되지 않는다. 건물과 건물이 맞닿아 있어도 그 사이에는 틈이 있어 지나갈 수 있다. 건물의 부지는 서로 겹치지 않는다.

야간 이용자의 안전을 지키기 위해 $a$명의 경비원이 좌표 $(x_1, y_1), \dots, (x_a, y_a)$에 배치되어 있다. 경비원의 배치 위치는 건물 밖이다.

심야에 Y 센터 안의 경비는 다음과 같이 이루어진다. 부지 안의 어떤 점에서 수상한 물건이 발견되면 그때마다 모든 경비원에게 연락이 간다. 그리고 그 점까지 이동 거리가 가장 짧은 경비원이 현장으로 급히 가서 수상한 물건을 확인한다. 경비원은 Y 센터 안을 최단 거리로 이동하지만, 건물 내부는 심야에 잠겨 있어 건물 내부를 지날 수 없다. (건물의 변은 건물에 포함되지 않으므로 건물의 변을 따라 이동할 수 있다) 수상한 물건의 확인이 끝나면 경비원은 같은 경로로 자기 위치로 돌아온다. 다음에 수상한 물건이 발견될 때도 마찬가지로 경비한다.

그림 2: 경비원이 현장으로 급히 가는 그림 (○이 경비원, ×가 수상한 물건)

어느 날 심야에 Y 센터 안 건물 밖에서 $c$개의 수상한 물건이 발견되었다. Y 센터의 크기, 경비원의 위치, 건물의 위치, 그리고 어느 날 심야에 발견된 수상한 물건의 위치 $(p_1, q_1), \dots, (p_c, q_c)$가 발견 시각 순서로 주어질 때, 경비원의 이동 거리 총합을 구하는 프로그램을 작성하시오.

입력의 첫째 줄에는 경비원의 수를 나타내는 정수 $a$ ($1 \le a \le 10$), 건물의 수를 나타내는 정수 $b$ ($1 \le b \le 50$), 수상한 물건의 수를 나타내는 정수 $c$ ($1 \le c \le 10$)가 쓰여 있다.

둘째 줄에는 Y 센터 부지의 크기를 나타내는 두 정수 $w, h$ ($1 \le w, h \le 1000$)가 가로, 세로 순서로 쓰여 있다.

$i + 2$번째 줄 ($1 \le i \le a$)에는 $i$번째 경비원의 위치를 나타내는 두 정수 $x_i, y_i$ ($0 \le x_i \le w$, $0 \le y_i \le h$)가 쓰여 있다. $j + a + 2$번째 줄 ($1 \le j \le b$)에는 $j$번째 건물의 위치를 나타내는 네 정수 $s_j, t_j, u_j, v_j$ ($0 \le s_j < u_j \le w$, $0 \le t_j < v_j \le h$)가 쓰여 있다. $k + a + b + 2$번째 줄 ($1 \le k \le c$)에는 $k$번째 수상한 물건의 위치를 나타내는 두 정수 $p_k, q_k$ ($0 \le p_a \le w$, $0 \le q_a \le h$)가 쓰여 있다.

출력은 표준 출력에 한다.

경비원의 이동 거리 총합을 소수점 아래 세 자리까지 출력하시오. 오차는 0.001 이하여야 한다.