In the world waiting to be lit

题目背景

题目描述

lhy 喜欢玩星穹铁道，他对其中的引航罗盘玩法十分感兴趣，因此想要与你一同研究。

你将会看到一个罗盘，其上均匀分布着n个点，顺时针依次记作$1,2,3,...,n$，内圈有k个指针，第i个指针的转速为$r_i$, 初始位置为$a_i$.

其中转速是指：经过一次旋转，该指针会经过r个点。例如当前指针在3处, 转速为2, 那么进行一次旋转后指针将会处于5处($n\ge 5$).

你每次需要指定两个指针，并使得它们同时旋转一次。问至少需要旋转多少次，可以使得所有指针都处于1处。如果无论如何都无法使得所有指针指向1，那么输出-1.

虽然在游戏中总是有$n = 6, k = 3$, 但是lhy 准备扩展一下，你将会得到$n \le 10^9, k \le 10^5$. 不过 lhy 还会补充两个条件。

1. 你所选择的两个指针可以是相同的.
2. $n$将会是一个素数.

数据格式

输入

第一行，两个正整数n,k.

接下来 k 行，每行两个正整数 $r_i,a_i$.

输出

一个正整数表示最少的旋转次数。

样例

输入

7 2
3 2
4 6

输出

6

数据范围及约定

$n \le 10^9, k \le 10^5$.

$1 \le a_i,r_i \le n$

$n$是一个素数.