分数: 500 点
问题陈述
我们有一个无向图 N 顶点和 0 边缘。 让我们调用 N 顶点 顶点 0,顶点 1,顶点 2, \ldots,顶点 N-1.
考虑 M 在此图上进行各种操作。
对于每个 i = 1, 2, \ldots, M,操作 i- 第一种是选择一个整数 x 这样 0 \leq x \lt N 并添加连接顶点的无向边 x 和顶点 (x + A_i) \bmod N。在这里, a \bmod b 表示除法时的余数 a by b。
它的成本 C_i 日元做的操作 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
如果我们先进行第一种连接顶点的操作 0 和 2,然后再次连接顶点 1 和 3,最后是第二种连接顶点的操作 1 和 0,图形将被连接。 这里产生的总成本是 3+3+5 = 11 日元,这是可能的最低金额。
示例输入 2
6 1 3 4
示例输出 2
-1
没有办法使图形连接起来,所以我们应该打印 -1.