시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 20 9 9 75.000%

문제

세준이는 위험한 지역에서 탈출하는 게임을 하고 있다. 이 게임에는 세준이가 들어갈 수 없는 죽음의 구역이 있고, 들어가서 한 번 움직일 때 마다 생명이 1씩 소모되는 위험한 구역이 있다. 그리고, 자유롭게 생명의 위협없이 움직일 수 있는 안전한 구역이 있다. (안전한 구역은 죽음의 구역과 위험한 구역을 제외한 나머지 이다.)

세준이는 (0, 0)에서 출발해서 (500, 500)으로 가야 한다. 세준이는 위, 아래, 오른쪽, 왼쪽으로만 이동할 수 있다. 현재 세준이는 (0, 0)에 있다. 그리고, 게임 판을 벗어날 수는 없다.

세준이가 (0, 0)에서 (500, 500)으로 갈 때 잃는 생명의 최소값을 구하는 프로그램을 작성하시오.
 

입력

첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 반대 모서리이다. 그 다음 줄에는 죽음의 구역의 수 M이 주어진다. 다음 줄부터 M개의 줄에는 죽음의 구역의 정보가 위험한 구역의 정보와 같이 주어진다. 주어지는 구역은 모두 겹칠 수 있으며, 서로 다른 구역이 겹칠 때는, 더 심한 구역이 해당된다. 예를 들어, 죽음+위험 = 죽음, 위험+안전 = 위험, 위험+위험 = 위험, 죽음+안전 = 죽음이다. 위험한 구역이 아무리 겹쳐도 생명은 1씩 감소된다. 생명의 감소는 구역에 들어갈 때만, 영향을 미친다. 예를 들어, (500, 500)이 위험한 구역일 때는, (500, 500)에 들어갈 때, 생명이 1 감소되지만, (0, 0)이 위험한 구역이더라도 생명은 감소되지 않는다. 마찬가지로, (0, 0)이 죽음의 구역이더라도 세준이는 이미 그 곳에 있으므로 세준이에게 영향을 미치지 않는다. N과 M은 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 출력한다. 만약 (500, 500)으로 갈 수 없을 때는 -1을 출력한다.

예제 입력

1
500 0 0 500
1
0 0 0 0

예제 출력

1000

힌트

출처