크립토나이트 광산

2222년, 화성의 한 크립토나이트 광산에서 끔찍한 재난이 일어났습니다. 그 지역에 화성지진이 발생한 것입니다. 지구의 지진과 달리 화성에서 화성지진은 드문 일이 아니지만, 이번 지진은 광산이 서서히 지반 속으로 가라앉게 만들었습니다.

광산의 외곽은 직사각형 모양이며, 내부는 높고 곧은 벽들로 이루어진 미로이고, 무엇보다도 순간이동 장치(텔레포터)가 있습니다. 텔레포터는 사람을 한 곳에서 다른 곳으로 즉시 이동시킬 수 있습니다. 이 광산의 텔레포터는 아주 오래된 구형 모델이어서, 두 부스 사이에 시야가 완전히 트여 있을 때에만(즉, 두 부스 사이를 가로막는 벽이 하나도 없을 때에만) 사람을 두 부스 사이로 이동시킬 수 있습니다.

당신은 광산 안에 홀로 갇혀 있습니다. 다행히 광산 전체의 지도를 가지고 있어 현재 위치, 모든 벽의 위치, 출구의 위치, 그리고 모든 텔레포터 부스의 위치를 알고 있습니다. 안타깝게도 화성지진으로 전력 계통이 손상되어, 텔레포터는 통틀어 정해진 횟수만큼만 사용할 수 있습니다.

지진 중에 발목을 삐었기 때문에, 당신은 가능한 한 적게 걸어서 출구에 도달하고 싶습니다. 벽을 통과해서 걸을 수는 없으며, 반드시 벽을 돌아가야 합니다. 현재 위치에서 출구까지 걷는 총 거리를 최소로 하는 경로를 찾으세요.

입력은 여러 개의 테스트 케이스로 이루어져 있습니다. 각 테스트 케이스의 첫 줄에는 세 정수 $N$, $M$, $L$이 주어집니다. 각각 텔레포터를 통틀어 사용할 수 있는 횟수, 광산 안의 벽의 개수, 텔레포터 부스의 개수를 뜻합니다($0 \le N, M, L \le 50$).

이어지는 $M$개의 줄에는 각각 네 정수 $X_1$, $Y_1$, $X_2$, $Y_2$가 주어지며, 한 벽의 두 끝점의 좌표를 나타냅니다. 벽의 두께는 무시하며, 어떤 두 벽도 서로 교차하지 않습니다($-20000 \le X_1 \le X_2 \le 20000$, $-20000 \le Y_1 \le Y_2 \le 20000$).

이어지는 $L$개의 줄에는 각각 두 정수 $X_p$, $Y_p$가 주어지며, 한 텔레포터 부스의 좌표를 나타냅니다.

각 테스트 케이스의 마지막 줄에는 네 정수 $X_b$, $Y_b$, $X_e$, $Y_e$가 주어집니다. $(X_b, Y_b)$는 당신의 시작 위치이고 $(X_e, Y_e)$는 광산의 출구입니다.

입력의 끝은 $N = M = L = 0$인 줄로 표시되며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력합니다. 광산을 빠져나가기 위해 걸어야 하는 최소 거리입니다. 텔레포터로 이동한 거리는 포함하지 않습니다. 거리는 가장 가까운 정수로 반올림하여 출력합니다.