Fat Guys' Weight Synchronization

There are n fat guys. Initially, on day \(0\), each fat guy's weight is \(1\). For the \(i\)th fat guy, his weight on day \(t\) is \(w_i(t)\), and initially \(w_i(0)=1\). Each fat guy has his own multiplicative factor \(k_i\) and a "wake-up weight" \(g_i\). Every morning the fat guy multiplies his previous day's weight by \(k_i\). That is, if his weight on day \(t-1\) is \(w_i(t-1)\), then after waking up his weight becomes \(w_i(t-1)\times k_i\). However, if his weight exceeds \(g_i\), he goes to the gym and repeatedly subtracts \(g_i\) from his weight until his weight is no more than \(g_i\).

In mathematical terms, the daily update for the \(i\)th fat guy is defined as follows:

[ w_i(0)=1,\quad w_i(t)=\begin{cases} w_i(t-1)\times k_i, &\text{if }w_i(t-1)\times k_i\le g_i,\[1mm] w_i(t-1)\times k_i - \left\lfloor\frac{w_i(t-1)\times k_i-1}{g_i}\right\rfloor \times g_i, &\text{if }w_i(t-1)\times k_i>g_i. \end{cases} ]

Equivalently, one may write the update formula as:

[ w_i(t)=\Bigl(((w_i(t-1)\times k_i-1) \bmod, g_i) +1\Bigr). ]

Given a target sequence \(\{r_1,r_2,\ldots,r_n\}\), determine the minimum number of days \(t\) (with \(t\ge0\)) such that for all \(1\le i\le n\), \(w_i(t)=r_i\). If no such day exists, output -1.

inputFormat

The input begins with a line containing an integer n (the number of fat guys).

The second line contains n space-separated integers \(r_1,r_2,\ldots,r_n\), representing the target weight for each fat guy.

Then follow n lines. The \(i\)th of these lines contains two space‐separated integers \(k_i\) and \(g_i\), representing the multiplicative factor and the wake-up weight of the \(i\)th fat guy respectively.

outputFormat

Output a single integer: the minimum number of days needed for the fat guys' weights \(\{w_1(t), w_2(t), \ldots, w_n(t)\}\) to exactly match the target sequence \(\{r_1, r_2, \ldots, r_n\}\). If no such day exists, output -1.

sample

2
2 3
2 3
3 4

1