在 Polycarp 居住的大楼中,每层的公寓数量相同。不幸的是,波利卡普不记得每层楼有多少套公寓,但他记得公寓从下层到上层从1开始编号。即,前几套公寓位于一楼,接下来的几套公寓位于二楼,以此类推。波利卡普不记得建筑物中的公寓总数,因此您可以认为建筑物无限高(即有无限多个楼层)。请注意,楼层从 1 开始编号。
Polycarp 记得几套公寓位于哪一层。保证该信息不会自相矛盾。这意味着存在一栋每层公寓数量相同的建筑物,因此波利卡普记忆中的公寓具有波利卡普记忆中的楼层。
根据这些信息,是否可以恢复 n 号公寓的准确楼层?
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 100, 0 ≤ m ≤ 100),其中 n 是需要恢复楼层的公寓编号,m 是 Polycarp 内存中的公寓数量。
m 行,描述波利卡普的记忆:每一行包含一对整数 ki, fi (1 ≤ ki ≤ 100, 1 ≤ fi ≤ 100),这意味着平坦的 ki 位于第 fi 层。所有值 ki 都是不同的。
保证所提供的信息不自相矛盾。
输出
如果可以通过唯一的方式确定,则打印第 n 套公寓所在的楼层号。如果无法唯一恢复该楼层,则打印 -1。
示例
输入 #1
10 3 6 2 2 1 7 3
输出 #1
4
输入 #2
8 4 3 1 6 2 5 2 2 1
输出 #2
-1
注意
在第一个示例中,第 6 套公寓位于 2 楼,而第 7 套公寓位于 3 楼,因此,第 6 套公寓是该楼层的最后一个公寓,每层有 3 套公寓。因此,第 10 套公寓位于 4 楼。
在第二个示例中,每层可以有 3 或 4 套公寓,因此我们无法恢复第 8 套公寓的楼层。