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)$。

输出格式

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

输入输出样例 #1

输入 #1

4 2
2 3
3 5

输出 #1

11

输入输出样例 #2

输入 #2

6 1
3 4

输出 #2

-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。