시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 78 16 8 21.622%

문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 원숭이는 최근 철도청 국장에게 특별 프로젝트 수행을 제의받고 철도청에 근무하고 있다. 그런데 프로젝트를 수행하던 도중, 심각한 문제에 부딪쳤다. 원숭이는 이것을 혼자 해결할 능력이 부족하다. 일단 원숭이가 해결해야하는 문제가 무엇인지 알아보자.

해결해야 하는 문제는 다음과 같다. 화물열차가 두 대가 있을 때, 이웃한 레일 위에 놓인 두 화물 열차 사이에 짐을 옮기려고 한다. 화물 열차의 각 칸에는 컨테이너가 놓여 있기도 하고, 놓여 있지 않기도 한데 컨테이너가 놓인 칸이 가장 많이 겹치도록 두 화물 열차를 겹쳐 놓으면 짐을 옮기는 과정이 수월하다.

처음에 두 화물 열차는 아래 그림과 같이 첫 칸의 앞부분이 서로 마주보며 같은 선에 위치하고 있다. 화물 열차 A는 가만히 있고, 화물 열차 B를 움직여 컨테이너가 놓인 칸이 가능한 많이 겹쳐지게 하려고 한다. 화물 열차 B를 몇 칸 앞으로 움직여야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 화물 열차 A에 연속적으로 컨테이너가 놓여 있는 구간의 개수 N이 주어진다. 이어 N줄에는 Xi와 Yi (Xi ≤ Yi)가 공백을 사이에 두고 주어지는데 이는 화물 열차 A의 Xi칸부터 Yi칸까지 컨테이너가 놓여 있음을 의미한다. 다음 줄에는 화물 열차 B에 연속적으로 컨테이너가 놓여 있는 구간의 개수 M이 주어진다. 이어 M줄에는 Zi와 Wi (Zi ≤ Wi)가 공백을 사이에 두고 주어지는데 이는 화물 열차 B의 Zi칸부터 Wi칸까지 컨테이너가 놓여 있음을 의미한다. N과 M은 1,000이하의 자연수이고, Xi, Yi, Zi, Wi는 109이하의 자연수이다.

출력

첫째 줄에 두 열차의 컨테이너가 놓인 칸이 최대로 겹쳐지게 하기 위하여 화물 열차 B를 몇 칸 앞으로 움직여야 하는지를 출력한다. 최대로 겹쳐지게 하도록 열차 B를 움직이는 칸수가 여러 가지인 경우에는 그 중 최소값을 출력한다.

예제 입력

3
1 3
5 5
7 9
3
2 3
6 6
8 9

예제 출력

10

힌트