AT_abc210_e [ABC210E] Ring MST

- 给定一张 $n$ 个点的图，顶点的编号为 $[0, n - 1]$，同时给出两个长度为 $m$ 的数组 $a_1, a_2, \cdots, a_m$ 和 $b_1, b_2, \cdots, b_m$。 - 初始时图中并没有任何边，你可以按照以下操作加边：选择一个 $1 \le i \le m$ 和一个 $0 \le x < n$，并在顶点 $x$ 和顶点 $(x + a_i) \bmod n$ 中添加一条长度为 $b_i$ 的边。 - 你现在想要知道，你添加的边的长度总和至少为多少，才能使得整个图连通?如果无论如何都不能使整个图连通，输出 `-1`。

- 第一行包含两个整数 $n, m$，分别表示图的顶点个数和数组的数组的长度。 - 接下来 $m$ 行，第 $i$ 行包含两个整数 $a_i, b_i\space(1 \le a_i \le n - 1)$。

- 输出一个数，表示答案。

- 对于 $30 \%$ 的数据：$1 \le n, m \le 1000, 1 \le b_i \le 10^9$。 - 对于 $60 \%$ 的数据：$1 \le n, m \le 10^5, 1 \le b_i \le 10^9$。 - 对于 $100 \%$ 的数据：$1 \le n \le 10^9, 1 \le m \le 10^5, 1 \le b_i \le 10^9$。 翻译提供者：[Sunrize](https://www.luogu.com.cn/user/502658)。