동물원 확장

네버랜드는 한국에서 가장 큰 동물원이다. 동물원은 야생에 가까운 생태 단지를 만들기 위해 근처 부지를 새로 샀다.

이 동물원에서 가장 인기 있는 동물은 원숭이다. 원숭이는 점프하거나 나무를 기어오르는 모습으로 방문객들을 즐겁게 한다.

원숭이는 두 종류로 나뉜다. 첫 번째 종류는 나무에 올라 코코넛을 따는 데 특화되어 있고, 두 번째 종류는 코코넛을 여는 데 특화되어 있다.

첫 번째 종류의 원숭이는 총 N마리, 두 번째 종류의 원숭이는 총 M마리이며, 각 종류 안에서 원숭이는 1번부터 번호가 매겨진다.

첫 번째 종류의 k번째 원숭이는 오를 나무를 찾고 첫 코코넛을 따는 데 A_k초가 걸린다. 그 뒤에는 B_k초마다 코코넛을 하나씩 더 딴다.

두 번째 종류의 k번째 원숭이는 좋은 도구를 찾고 첫 코코넛을 여는 데 C_k초가 걸린다. 그 뒤에는 D_k초마다 코코넛을 하나씩 더 열 수 있다.

두 종류의 원숭이는 사이가 좋지 않아 같은 장소에 동시에 있을 수 없다. 그래서 사육사는 첫 번째 종류가 모든 코코넛을 따는 즉시 그들을 우리로 돌려보내고, 바로 두 번째 종류를 생태 단지로 부른다.

사육사는 첫 번째 종류가 모든 코코넛을 따는 순간 도착한다. 원숭이를 우리로 보내거나 우리에서 불러오는 데 걸리는 시간은 무시할 수 있다.

상근이는 두 번째 종류의 원숭이를 매우 좋아하지만 언제 가야 볼 수 있는지 모른다. 두 종류의 원숭이가 생태 단지에 머문 전체 시간 T가 주어질 때, 두 번째 종류의 원숭이가 생태 단지에 들어오는 시간을 구하시오. 상근이는 전체 코코넛 개수를 알지 못한다.

첫째 줄에 원숭이가 생태 단지에 머문 전체 시간 T가 주어진다. (1 <= T <= 1,000,000,000)

둘째 줄에 첫 번째 종류의 원숭이 수 N이 주어진다. (1 <= N <= 100)

다음 N개 줄에는 k번째 원숭이의 정보 A_k와 B_k가 주어진다. (1 <= A_k, B_k <= 1,000,000,000)

그다음 줄에 두 번째 종류의 원숭이 수 M이 주어진다. (1 <= M <= 100)

다음 M개 줄에는 k번째 원숭이의 정보 C_k와 D_k가 주어진다. (1 <= C_k, D_k <= 1,000,000,000)

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

전환 시간이 X초라면, X초에 여러 마리의 원숭이가 동시에 코코넛을 딸 수 있다. 따라서 첫 번째 종류가 정확히 X초에 마지막으로 딴 코코넛 개수의 가능한 범위와, 두 번째 종류가 T-X초 동안 마지막으로 열 수 있는 코코넛 개수의 가능한 범위가 겹치는지 확인해야 한다.