该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

To irrigate the wilderness that's still asleep

题目背景

题目描述

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$.

选取两个指针同时旋转一次，最终旋转次数算作两次。

数据格式

输入

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

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

输出

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

样例

输入

6 3
1 1
2 3
3 4

输出

10

数据范围及约定

$n = 6, k = 3$.

$1 \le a_i,r_i \le n$