← 返回题目列表

Codeforces · 858/B

B. 几楼?

中文机器翻译题面 查看原题

在 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 套公寓的楼层。