### COCI 2008/2009, Contest #2

## Task SVADA

The local zoo has acquired a large open garden in which animals may freely move as in their natural habitats and entertain visitors with their usual shenanigans.

The most popular animals are monkeys. With their climbing and jumping and other skills, they delight old and young visitors alike.

One species of monkey has specialized in climbing tall trees and picking off coconuts. Another species has specialized in breaking them open.

There are N monkeys of the first type (numbered 1 through N) and M monkeys of the second type (numbered 1 through M).

Monkey k of the first type takes A_{k} seconds to find a good spot on the tree, after which it picks off its
first coconut. After that the monkey produces a new coconut every B_{k} seconds.

Monkey k of the second type takes C_{k} seconds to find a good spot on the tree, after which it picks off
its first coconut. After that the monkey produces a new coconut every D_{k} seconds.

Unfortunately, the second type of monkey is extremely aggressive so the two types may not be in the garden at the same time. Therefore, zoo keepers will chase away the first type of monkeys as soon as they have picked off all the coconuts. Similarly, if monkeys of the same type stay too long after opening all the coconuts, fights will ensue. Because of that, zoo keepers will send them away as soon as they have opened all the coconuts.

The zoo keepers first arrive immediately after all coconuts have been picked, and again immediately after the monkeys open them all. The time needed for monkeys to enter or leave the garden is also negligibly small.

Tomislav especially likes the second type of monkey, but can never guess when to arrive in order to see
them. Help him calculate the time when the second type arrives if he knows the **total time that
monkeys spent in the garden**, but **does not know the number of coconuts** in the garden.

### Input

The first line contains the integer T (1 ≤ T ≤ 1,000,000,000), the total time that monkeys spent in the
garden, in seconds.

The next line contains the integer N (1 ≤ N ≤ 100), the number of monkeys of the first type.

Each of the following N lines contains two integers A_{k} and B_{k} (1 ≤ A_{k}, B_{k} ≤ 1,000,000,000), how fast
monkey k of the first type is.

The next line contains the integer M (1 ≤ M ≤ 100), the number of monkeys of the second type.

The following M lines contain two integers C_{k} and D_{k} (1 ≤ C_{k}, D_{k} ≤ 1,000,000,000), how fast
monkey k of the second type is.

### Output

Output the number of seconds between the arrival of the first type of monkeys and the arrival of the second type.### Examples

## Input12 1 3 1 1 5 1 ## Output5 |
## Input20 2 3 2 1 3 3 3 1 4 1 5 1 ## Output13 |

In the first example, it turns out there are three coconuts in the garden:

- The monkey of the first type picks off the first coconut 3 seconds after the garden was opened.
- The monkey picks off the second coconut 4 seconds after the garden is opened.
- The monkey picks off the third coconut 5 seconds after the garden is opened.
- Zoo keepers come in and escort the monkey out. The monkey of the second type arrives. The output is 5 because this is when Tomislav wants to arrive.
- The monkey of the second type opens the first coconut 10 seconds after the garden was opened.
- The monkey opens the second coconut 11 seconds after the garden was opened.
- The monkey opens the third coconut 12 seconds after the garden was opened.
- Zoo keepers come in and escort the monkey out.

All Submissions

Best Solutions

**Point Value:** 10

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Nov 21, 2008

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

jeffreyxiaoon Jan 09, 2015 - 2:29:55 pm UTC Typo?pibombon Jan 10, 2015 - 3:56:18 am UTC Re: Typo?