시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 8 3 2 50.000%

문제

네버랜드는 한국에서 가장 큰 규모를 자랑하는 동물원이다. 이번에 이 동물원은 야생 상태와 흡사한 생태 단지를 만들기 위해서 근처 부지를 구입했다.

동물원에서 가장 인기있는 동물은 원숭이이다. 원숭이는 점프하고 나무를 기어 오르는 것과 같은 기술을 이용해서 남녀노소 모든 방문객을 즐겁게 해준다.

원숭이는 크게 두 종으로 나눌 수 있다. 한 종은 나무를 오르고, 코코넛을 따는 것에 특화되어 있는 종이고, 다른 종은 코코넛을 여는데 특화되어있다.

첫 번째 원숭이 종은 총 N마리, 두 번째는 M마리가 있다. 번호는 둘다 모두 1부터 N까지 매겨져 있다.

첫 번째 종의 원숭이 중 k번째 원숭이는 오를 나무를 찾아 첫 코코넛을 따는데 Ak초가 걸린다. 이후에 Bk초마다 새로운 코코넛을 생산한다.

두 번째 종의 원숭이 중 k번째 원숭이는 코코넛을 여는 좋은 도구를 찾고, 첫 코코넛을 여는데 Ck초가 걸린다. 이후 Dk초마다 새로운 코코넛을 열 수 있다.

안타깝게도, 두 원숭이 종은 서로 사이가 좋지 않기 때문에 동시에 같은 장소에 있을 수 없다. 따라서, 동물원 사육사는 첫 번째 원숭이 종이 코코넛을 모두 따면 즉시 우리로 돌려 보내고 두 번째 종을 부를 것이다.

동물원 사육사는 첫 번째 종이 모든 코코넛을 따는 즉시 도착한다. 우리로 보내는 시간과 우리에서 원숭이를 불러오는 시간은 무시할 수 있을 만큼 매우 작다.

상근이는 두 번째 종을 매우 좋아한다. 하지만, 언제 가야 되는지를 모르고 있다. 원숭이가 생태 단지에 있는 전체 시간이 주어졌을 때, 언제 도착하면 두 번째 원숭이를 볼 수 있는지 구하는 프로그램을 작성하시오. 상근이는 전체 코코넛의 개수를 알 수 없다.

입력

첫째 줄에 원숭이가 생태 부지에 있는 전체 시간 T (1 ≤ T ≤ 1,000,000,000)가 주어진다.

둘째 줄에는 첫 번째 원숭이의 수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개 줄에는 k번째 원숭이의 정보 Ak와 Bk가 주어진다. (1 ≤ Ak, Bk ≤ 1,000,000,000)

다음 줄에는 두 번째 원숭이의 수 M이 주어진다. (1 ≤ M ≤ 100)

다음 M개 줄에는 k번째 원숭이의 정보 Ck와 Dk가 주어진다. (1 ≤ Ck, Dk, ≤ 1,000,000,000)

출력

첫째 줄에 첫 번째 종이 우리로 들어가는 시간이자 두 번째 종이 생태 단지로 들어오는 시간을 출력한다.

예제 입력

12
1
3 1
1
5 1

예제 출력

5

힌트

예제의 경우는 코코넛이 세 개 있는 경우다.

첫 번째 종은 한 마리다. 이 원숭이가 나무를 올라서 첫 코코넛을 따는데 걸리는 시간은 3초이다. 그 다음 4초에 두 번째 코코넛을 따며, 5초에 세 번째 코코넛을 딴다.

사육사는 문을 연지 5초가 지났을 때, 생태 단지에 들어와서 첫 원숭이를 우리로 돌려보내고 두 번째 종을 생태 단지로 불러온다. 이 시간부터 두 번째 종을 볼 수 있기 때문에 정답은 5이다.

문을 연 시간부터 10초가 지나면 도구를 찾고 첫 코코넛을 따고, 11초에 두 번째 코코넛, 12초에 세 번째 코코넛을 딴다. 이제 사육사가 들어와서 다시 원숭이를 우리로 돌려 보낸다.