Problem J
Modulo Solitaire

Modulo Solitaire is a game that can be played when you are bored. You can even play it without a phone, just on paper. First, you pick a number $m$. Then you pick two sequences of numbers $a_{i}$ and $b_{i}$. Finally, you pick a starting number $s_{0}$. Now, your goal is to go from $s_{0}$ to $0$ in as few moves as possible. In each move, you choose an $i$, then multiply your current number by $a_{i}$, add $b_{i}$ to it, and reduce the result modulo $m$. That is, $s_{j} = (s_{j-1} \cdot a_{i_{j}} + b_{i_{j}}) \bmod {m}$.

Input

The first line of input contains three integers $1 \le m \le 10^6$, $0 \le n \le 10$, and $1 \le s_{0} < m$. The next $n$ lines each contain two integers, a pair $0 \le a_ i \le 10^9$ and $0 \le b_ i \le 10^9$.

Output

Output a single integer, the minimum number of moves needed to reach $0$ starting from $s_0$. If it is not possible to reach $0$ in any number of moves, output $-1$.

5 2 1
2 1
3 1

2