Minimum Global Attack Count

A robot is programmed to fight through n dragons in sequence. The i-th dragon has an initial health value a_i and a recovery ability: when activated, its health increases by p_i each time until its health becomes non‐negative. A dragon only dies if, after the attack phase, its health is exactly 0 (either immediately or right after some recovery step).

The robot is given m swords initially. Each sword has a fixed attack power. When facing a dragon, the robot chooses exactly one sword from those currently available according to the following rule:

• If there exists at least one sword whose attack power is not greater than the dragon’s initial health a_i, then the robot picks the one with the maximum such attack power.
• If all available swords have attack powers greater than a_i, then the robot picks the sword with the minimum attack power.

Once the robot finishes fighting a dragon, the sword used is discarded; however, as a reward a brand‐new sword is obtained. (Note that the reward sword is exactly the same as the one that was used, so the multiset of sword attack powers remains unchanged throughout the game.)

The fighting process against each dragon is as follows:

1. The robot attacks the dragon exactly x times with the chosen sword (with attack power ATK). Thus, the dragon’s health is reduced by x × ATK, resulting in a post‐attack health of a_i − x × ATK.
2. After the attack phase, if the health is exactly 0 the dragon dies immediately. Otherwise, if the health is negative, the dragon repeatedly uses its recovery ability: its health increases by p_i at a time until the health becomes non–negative. If at any moment before a recovery or after a recovery the dragon’s health is exactly 0, the dragon dies. (If the health is positive at the end of the attack phase, no recovery is performed and the dragon survives.)

Your task is to choose the minimum positive integer x (attack count per dragon) such that following the robot’s rules the robot can defeat every dragon in order. If no such x exists, output -1.

Note: For each dragon with parameters a, p and the chosen sword with attack power ATK, the following must hold for the dragon to die:

• x × ATK ≥ a (so the dragon’s health is not positive after the attack phase), and
• If x × ATK = a, the dragon dies immediately; otherwise, if x × ATK > a (so the health after attack is negative), then it is necessary that x × ATK − a is an exact multiple of p (i.e. there exists a nonnegative integer k such that a − x × ATK + k×p = 0).

Input details and sword selection make the problem non–trivial since the condition for each dragon becomes:

ATK × x ≡ a (mod p) with x ≥ ceil(a/ATK)

Your overall task is to find the minimum x satisfying all of these congruence conditions simultaneously (one for each dragon, using the appropriate chosen sword). If no such x exists, output -1.

inputFormat

The first line contains two integers n and m — the number of dragons and the number of swords.

The second line contains m integers representing the attack powers of the swords.

Then, n lines follow, each containing two integers a_i and p_i — the initial health and recovery value of the i-th dragon.

outputFormat

Output a single integer — the minimum global attack count x required per dragon so that the robot can defeat all dragons in order, or -1 if it is impossible.

sample

2 3
3 5 7
10 5
20 4

20