著名的海盗团伙“海狗”从一次奢侈的掠夺中回到了他们的藏身之处。他们希望在他们之间公平地分配他们的财富,这就是为什么你,他们值得信赖的财务顾问,设计了一个游戏来帮助他们:
所有人都坐在圆桌旁,其中一些人拿着刚刚偷来的金币。在游戏的每次迭代中,如果其中一个人拥有等于或超过 2 个硬币,他就有资格分配,并且他会给坐在他旁边的每个海盗一枚硬币。如果有更多候选者(拥有等于或超过 2 个硬币的海盗),那么您就是选择其中哪一位将在该迭代中进行分割的人。当没有更多的候选人有资格进行分裂时,游戏结束。
只有当游戏结束时,海盗才可以收工。由于他们是可支配时间有限的生物,他们更希望自己正在玩的游戏能够在有限的迭代后结束,如果是这样,他们称其为好游戏。另一方面,如果无论你如何进行分裂,游戏都不能以有限迭代结束,他们称其为糟糕的游戏。你能在他们开始玩游戏之前帮助他们弄清楚游戏是好是坏吗?
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^{9}$$$, $$$0 \le k \le 2\cdot10^5$$$),其中 $$$n$$$ 表示海盗总数,$$$k$$$ 表示拥有金币的海盗数量。
接下来的 $$$k$$$ 输入行包含整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i \le n$$$, $$$1 \le b_i \le 10^{9}$$$),其中 $$$a_i$$$ 表示坐在圆桌旁的海盗的索引 ($$$n$$$ 和$$$1$$$ 是邻居),$$$b_i$$$ 是海盗 $$$a_i$$$ 在游戏开始时拥有的硬币总数。
输出
如果游戏是一个好游戏,则打印 $$$1$$$: 有一种方法可以进行分割,以便游戏在有限次数的迭代后结束。
如果游戏是一个糟糕的游戏,则打印$$$-1$$$:无论你如何进行分割,游戏都不会以有限的迭代次数结束。
示例
输入 #1
4 2 1 2 2 2
输出 #1
1
输入 #2
6 2 2 3 4 1
输出 #2
1
输入 #3
3 2 1 1 2 2
输出 #3
-1
注意
在第三个例子中,游戏没有结束,因为你总是只有一个候选人,在他分裂之后,你最终会处于与起始候选人相同的位置。