题目描述

在一个神秘的魔法世界里，有一个环形城镇，这个城镇由 $N$ 座城堡组成，按顺时针方向编号为 $0$ 到 $N-1$。最初，这些城堡之间没有任何道路连接，你需要通过施放魔法来建立道路，使得所有城堡最终可以互相到达。

魔法协会提供了 $M$ 种建造道路的法术，每种法术的施放方式如下：

• 选择一个城堡 $x$（$0 \leq x < N$）。
• 施放该法术后，会在 城堡 $x$ 和 城堡 $(x + A_i) \mod N$ 之间建立一条双向道路。
• 每种法术的施放都会消耗 $C_i$ 点魔力值。

你可以任意多次（包括0次）施放这些法术，以任意顺序施放。

你的目标是：

• 判断是否可以通过施放这些法术，使得所有城堡最终可以互相到达（即形成一个连通图）。
• 如果可以，请计算实现这一目标所需的最小魔力消耗；如果不可能，请输出 -1。

输入格式

输入由标准输入提供，格式如下：

• 第一行包含两个整数 $N$（城堡数量）和 $M$（可用的魔法种类）。
• 接下来 $M$ 行，每行包含两个整数 $A_i$ 和 $C_i$，表示第 $i$ 种法术：
  • 该法术可以连接编号 $x$ 和 $(x + A_i) \mod N$ 的城堡。
  • 施放该法术一次需要消耗 $C_i$ 点魔力。

输出格式

如果可以使所有城堡连通，输出所需的最小魔力值；否则，输出 -1。

样例

4 2
2 3
3 5

11

6 1
3 4

-1

说明

对于样例1：

• 施放第一种法术，连接 城堡 0 和 城堡 2，消耗 3 点魔力。
• 再次施放第一种法术，连接 城堡 1 和 城堡 3，再消耗 3 点魔力。
• 施放第二种法术，连接 城堡 1 和 城堡 0，消耗 5 点魔力。

最终城堡连通，总消耗魔力值 $3 + 3 + 5 = 11$，是最优解。

对于样例2：

仅能连接 $(x, (x+3) \mod 6)$，形成$(0,3), (1,4), (2,5)$三个独立的环，无法让所有城堡连通，因此输出 -1。

数据范围

• $2 \leq N \leq 10^9$
• $1 \leq M \leq 10^5$
• $1 \leq A_i \leq N-1$
• $1 \leq C_i \leq 10^9$
• 所有输入值均为整数。