← 返回题目列表

AtCoder · abc210_e

E. 环 MST

中文机器翻译题面 查看原题

分数: 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.