어느 동물원에 아주 큰 정원이 있다. 이 정원에는 매우 큰 코코넛 나무가 있다.

이 동물원에서 가장 유명한 동물은 원숭이다. 원숭이의 다양한 재주 때문에 많은 사람들이 모여들기 때문이다.

이 동물원에는 두 종류의 원숭이가 있다.

• 첫 번째 원숭이는 나무를 올라타서 코코넛을 따는 걸 잘한다.
• 반면에 두 번째 원숭이는 나무에서 떨어진 코코넛을 여는 걸 잘한다.

동물원에는 N마리의 첫 번째 원숭이가 있고 M마리의 두 번째 원숭이가 있다.

• 첫 번째 종의 원숭이 k는 나무에 좋은 자리를 잡고 첫 번째 코코넛을 떨어트리는데 Ak 초가 걸린다. 그 다음 Bk초마다 코코넛을 추가로 하나씩 더 떨어뜨린다.
• 두 번째 종의 원숭이 k는 코코넛을 열기 좋은 도구를 찾고 첫 번째 코코넛을 여는 데 Ck초가 걸린다. 그 다음 Dk초마다 코코넛을 추가로 하나씩 더 연다.

불행하게도 두 번째 종의 원숭이는 매우 공격적이어서 첫 번째 종류의 원숭이와 같이 있으면 안 된다. 그래서 첫 번째 원숭이가 나무에서 코코넛을 다 떨어트리면 바로 정원에서 퇴장한다.

그 다음 바로 두 번째 원숭이가 정원에 들어와 첫 번째 원숭이가 떨어트린 코코넛을 열기 시작한다. 그리고 마지막 코코넛을 열면 바로 정원에서 퇴장한다.

톰은 특별히 두 번째 원숭이를 좋아한다. 그래서 그는 두 번째 원숭이가 정원에 들어오는 시간을 알고 싶어 한다. 두 종류의 원숭이가 정원에 있는 총 시간 T가 주어질 때 두 번째 원숭이가 정원에 들어오는 시간을 구하는 게 문제이다. (코코넛 개수는 주어지지 않는다)

입력

• 첫 번째 줄은 정수 T(1<=T<=1 000 000 000)가 주어진다. T는 두 종류에 원숭이가 정원에 있는 총 시간이다.
• 두 번째 줄은 첫 번째 종류 원숭이 숫자인 정수 N(1<=N<=100)이 주어진다.
• 다음 N줄은 각 원숭이의 Ak, Bk 가 주어진다.
• 그 다음 줄은 두 번째 종류 원숭이 숫자인 정수 M(1<=M<=100)이 주어진다.
• 다음 M줄은 각 원숭이의 Ck, Dk 가 주어진다.

출력

입출력 예

입력

20
2
3 2
1 3
3
3 1
4 1
5 1

출력 

13

입출력 예 설명

첫 번째 종류의 원숭이가 11개의 코코넛을 떨어트리는데 총 13초가 걸린다. (그래서 답이 13)

두 번째 종류의 원숭이가 11개의 코코넛을 여는데 총 7초가 걸린다.

출처: COCI 2008-2009 November Contest Q4
번역: likepad