시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB73922711530.585%

문제

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

처음에 두 화물 열차는 아래 그림과 같이 첫 칸의 앞부분이 서로 마주보며 같은 선에 위치하고 있다. 화물 열차 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를 움직이는 칸수가 여러 가지인 경우에는 그 중 최솟값을 출력한다.

예제 입력 1

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

예제 출력 1

10