题目描述

我们有一个 $N$ 个顶点和 $0$ 条边的无向图。我们将这 $N$ 个顶点称为 Vertex $0$，Vertex $1$，Vertex $2$，$\\ldots$，Vertex $N-1$。

考虑在该图上进行 $M$ 种操作。
对于每个 $i = 1, 2, \\ldots, M$，第 $i$ 种操作是选择一个整数 $x$，满足 $0 \\leq x \\lt N$，并添加一条连接 Vertex $x$ 和 Vertex $(x + A_i) \\bmod N$ 的无向边。这里，$a \\bmod b$ 表示将 $a$ 除以 $b$ 得到的余数。第 $i$ 种操作的成本为 $C_i$ 日元。

你可以以任意顺序任意次数地执行这 $M$ 种操作（可能为零）。例如，如果有三种操作可用，你可以选择执行第一种操作两次、第二种操作零次和第三种操作一次。

确定是否可以使图连通。如果可能，找到使图连通所需的最小总成本。

约束条件

• $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$
• 输入中的所有值都是整数。

输入

从标准输入读入输入数据，具体格式如下：

$N$ $M$ $A_1$ $C_1$ $A_2$ $C_2$ $\\vdots$ $A_M$ $C_M$

输出

如果可以使图连通，请打印使图连通所需的最小总成本。
如果无法使图连通，请打印 $\-1$。

示例输入 1

4 2
2 3
3 5

示例输出 1

11

如果我们首先执行第一种操作来连接 Vertex $0$ 和 Vertex $2$，然后再执行一次来连接 Vertex $1$ 和 Vertex $3$，最后执行第二种操作来连接 Vertex $1$ 和 Vertex $0$，则图将连通。这里产生的总成本为 $3+3+5 = 11$ 日元，这是最小可能的成本。

示例输入 2

6 1
3 4

示例输出 2

-1

无法使图连通，因此应该打印 $\-1$。