레이팅 미적용동네 동물원이 넓은 개방형 정원을 새로 마련했다. 동물들은 자연 서식지에서처럼 자유롭게 돌아다니며 평소의 장난으로 방문객들을 즐겁게 할 수 있다.
가장 인기 있는 동물은 원숭이다. 나무 타기와 점프를 비롯한 온갖 재주로 남녀노소 방문객 모두를 즐겁게 한다.
원숭이 중 한 종은 높은 나무에 올라 코코넛을 따는 데 특화되어 있다. 다른 한 종은 코코넛을 깨서 여는 데 특화되어 있다.
첫 번째 종의 원숭이는 \(N\)마리(\(1\)부터 \(N\)까지 번호), 두 번째 종의 원숭이는 \(M\)마리(\(1\)부터 \(M\)까지 번호)가 있다.
첫 번째 종의 원숭이 \(k\)는 나무에서 좋은 자리를 찾는 데 \(A_k\)초가 걸리고, 그 후 첫 코코넛을 딴다. 그 다음부터는 \(B_k\)초마다 새 코코넛을 딴다.
두 번째 종의 원숭이 \(k\)는 코코넛을 열기 좋은 도구를 찾는 데 \(C_k\)초가 걸리고, 그 후 첫 코코넛을 연다. 그 다음부터는 \(D_k\)초마다 또 하나의 코코넛을 연다.
안타깝게도 두 번째 종의 원숭이는 극도로 공격적이어서 두 종이 동시에 정원에 있을 수 없다. 따라서 사육사들은 첫 번째 종의 원숭이들이 코코넛을 전부 따는 즉시 그들을 내보낸다. 마찬가지로 두 번째 종의 원숭이들이 코코넛을 전부 연 뒤에도 너무 오래 머무르면 싸움이 벌어지므로, 사육사들은 그들이 코코넛을 전부 여는 즉시 내보낸다.
사육사들은 코코넛이 전부 따진 직후에 처음 도착하고, 원숭이들이 코코넛을 전부 연 직후에 다시 도착한다. 원숭이들이 정원에 들어오고 나가는 데 걸리는 시간도 무시할 수 있을 만큼 짧다.
Tomislav는 두 번째 종의 원숭이를 특히 좋아하지만, 언제 가야 볼 수 있는지 도무지 짐작하지 못한다. 원숭이들이 정원에서 보낸 총 시간은 알지만 정원의 코코넛 개수는 모를 때, 두 번째 종이 도착하는 시각을 계산하도록 도와주자.
첫째 줄에 원숭이들이 정원에서 보낸 총 시간(초)인 정수 \(T\) (\(1 \le T \le 10^9\))가 주어진다.
다음 줄에 첫 번째 종 원숭이의 수인 정수 \(N\) (\(1 \le N \le 100\))이 주어진다.
다음 \(N\)개의 줄에는 두 정수 \(A_k\)와 \(B_k\) (\(1 \le A_k, B_k \le 10^9\))가 주어진다. 첫 번째 종의 원숭이 \(k\)의 빠르기이다.
다음 줄에 두 번째 종 원숭이의 수인 정수 \(M\) (\(1 \le M \le 100\))이 주어진다.
다음 \(M\)개의 줄에는 두 정수 \(C_k\)와 \(D_k\) (\(1 \le C_k, D_k \le 10^9\))가 주어진다. 두 번째 종의 원숭이 \(k\)의 빠르기이다.
첫 번째 종 원숭이들의 도착과 두 번째 종의 도착 사이의 시간(초)을 출력한다.
Contest #2, \(15^{th}\) November 2008
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 100점 |
12
1
3 1
1
5 1520
2
3 2
1 3
3
3 1
4 1
5 113