CF1423F.Coins

A famous gang of pirates, Sea Dogs, has come back to their hideout from one of their extravagant plunders. They want to split their treasure fairly amongst themselves, that is why You, their trusted financial advisor, devised a game to help them:

All of them take a sit at their round table, some of them with the golden coins they have just stolen. At each iteration of the game if one of them has equal or more than 2 coins, he is eligible to the splitting and he gives one coin to each pirate sitting next to him. If there are more candidates (pirates with equal or more than 2 coins) then You are the one that chooses which one of them will do the splitting in that iteration. The game ends when there are no more candidates eligible to do the splitting.

Pirates can call it a day, only when the game ends. Since they are beings with a finite amount of time at their disposal, they would prefer if the game that they are playing can end after finite iterations, and if so, they call it a good game. On the other hand, if no matter how You do the splitting, the game cannot end in finite iterations, they call it a bad game. Can You help them figure out before they start playing if the game will be good or bad?

一支著名的海盗团伙“海狗”刚刚从一次奢华的劫掠中返回他们的藏身之处。他们希望公平地分配战利品，因此你——他们信赖的财务顾问——设计了一个游戏来帮助他们：

所有海盗围坐在一张圆桌旁，其中一些人手中握有刚刚抢来的金币。在游戏的每一轮中，若某位海盗持有不少于 2 枚金币，则他具备“分发”资格，须向其左右两侧相邻的海盗各赠送 1 枚金币。若当前有多位具备资格的海盗（即持有不少于 2 枚金币者），则由你来决定本轮中由哪一位执行分发操作。当不再有任何具备分发资格的海盗时，游戏结束。

只有当游戏结束之后，海盗们才能收工休息。由于他们的时间是有限的，他们更希望所进行的游戏能在有限轮次内结束；若确实如此，则称该游戏为“好游戏”。反之，若无论你如何选择分发者，游戏都无法在有限轮次内结束，则称该游戏为“坏游戏”。在游戏开始之前，你能否帮他们判断：即将进行的游戏是“好游戏”还是“坏游戏”？

The first line of input contains two integer numbers $n$ and $k$ ($1 \le n \le 10^{9}$, $0 \le k \le 2\cdot10^5$), where $n$ denotes total number of pirates and $k$ is the number of pirates that have any coins.

The next $k$ lines of input contain integers $a_i$ and $b_i$ ($1 \le a_i \le n$, $1 \le b_i \le 10^{9}$), where $a_i$ denotes the index of the pirate sitting at the round table ($n$ and $1$ are neighbours) and $b_i$ the total number of coins that pirate $a_i$ has at the start of the game.

输入的第一行包含两个整数 $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$ 表示围坐在圆桌旁的第 $a_i$ 号海盗（编号 $n$ 与编号 $1$ 相邻），$b_i$ 表示该海盗 $a_i$ 在游戏开始时所拥有的金币总数。

Print $1$ if the game is a good game: There is a way to do the splitting so the game ends after finite number of iterations.

Print $-1$ if the game is a bad game: No matter how You do the splitting the game does not end in finite number of iterations.

如果该博弈是一个好博弈（即存在一种分割方式，使得博弈在有限次迭代后结束），则输出 $1$；
如果该博弈是一个坏博弈（即无论采用何种分割方式，博弈都无法在有限次迭代后结束），则输出 $-1$。

In the third example the game has no end, because You always only have only one candidate, after whose splitting you end up in the same position as the starting one.

在第三个例子中，游戏永远不会结束，因为您始终只有一个候选数，而对该候选数进行拆分后，得到的位置与初始位置完全相同。