Zoo Expansion

Neverland is the largest zoo in Korea. The zoo has bought nearby land to build an ecological area that resembles the wild.

The most popular animals in the zoo are monkeys. They entertain visitors by jumping and climbing trees.

There are two kinds of monkeys. The first kind is good at climbing trees and picking coconuts, and the second kind is good at opening coconuts.

There are N monkeys of the first kind and M monkeys of the second kind. Within each kind, the monkeys are numbered from 1.

For the k-th monkey of the first kind, it takes A_k seconds to find a tree and pick its first coconut. After that, it picks one more coconut every B_k seconds.

For the k-th monkey of the second kind, it takes C_k seconds to find a good tool and open its first coconut. After that, it can open one more coconut every D_k seconds.

Unfortunately, the two kinds of monkeys do not get along, so they cannot be in the same place at the same time. Therefore, as soon as the first kind has picked all coconuts, the keeper sends them back to their cage and immediately brings in the second kind.

The keeper arrives exactly when the first kind has picked all coconuts. The time needed to send monkeys back to the cage or bring them out is negligible.

Sanggeun really likes the second kind of monkeys, but he does not know when to visit. Given the total time T during which monkeys stay in the ecological area, determine the time when the second kind enters the area. Sanggeun does not know the total number of coconuts.

The first line contains the total time T that monkeys stay in the ecological area. (1 <= T <= 1,000,000,000)

The second line contains the number N of monkeys of the first kind. (1 <= N <= 100)

Each of the next N lines contains A_k and B_k for the k-th monkey. (1 <= A_k, B_k <= 1,000,000,000)

The next line contains the number M of monkeys of the second kind. (1 <= M <= 100)

Each of the next M lines contains C_k and D_k for the k-th monkey. (1 <= C_k, D_k <= 1,000,000,000)

Print the time when the first kind returns to the cage and the second kind enters the ecological area.

If the switch time is X seconds, several monkeys may pick coconuts at exactly second X. Therefore, compare the range of possible coconut counts completed by the first kind exactly at X with the range of possible counts that the second kind can finish exactly after T-X seconds.