CF1423F Coins

著名的海盗团伙 Sea Dogs 刚刚完成了一次盛大的掠夺，回到了他们的藏身处。他们希望能公平地分配战利品，因此你，作为他们信任的财务顾问，设计了一个游戏来帮助他们： 所有海盗围坐在一张圆桌旁，有些人手里拿着刚抢来的金币。在游戏的每一轮中，如果某个海盗手中的金币数量不少于 $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$ 表示坐在圆桌上的第 $a_i$ 号海盗（$n$ 号和 $1$ 号是相邻的），$b_i$ 表示第 $a_i$ 号海盗初始时拥有的金币数量。

如果游戏是“好游戏”，即存在一种分配顺序使得游戏能在有限轮内结束，输出 $1$。 如果游戏是“坏游戏”，即无论如何分配，游戏都无法在有限轮内结束，输出 $-1$。

在第三个样例中，游戏无法结束，因为你每次只有一个候选人，分配后又回到初始状态，陷入死循环。 由 ChatGPT 4.1 翻译