Better Together!

There are $N$ cities and initially $0$ roads between them. You are the Civil Engineer (but a programmer from heart!) who is in charge of constructing roads between these cities.

The cities are numbered from $0$ to $N - 1$. There are $M$ types of road constructions which can be performed among these cities. For each $k = 1, 2, 3, …, M$, the $k$-th kind of road construction is to choose an integer $x$ such that $0 \le x < N$ and construct a new two-way road connecting city $x$ and city $(x + A_k)\text{ mod } N$. Performing the $k$-th kind of road construction once costs $C_k$ taka.

You can do these $M$ kinds of road constructions any number of times (possibly zero) in any order. For example, if three kinds of road constructions are available, you can choose to perform the first type of road construction twice, the second zero times, and the third once.

The people of these cities want to travel from one city to another city. You have to determine whether it is possible to make all the cities connected together. If possible, then determine the minimum total cost. Here, “connected” means, there exists at least one path from each city to every other city.

Constraints:

• $2\le N\le10^9$
• $1\le M\le 10^5$
• $1\le A_k\le N - 1$
• $1\le C_k\le 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

If it is possible to make all the cities connected, print the minimum total cost needed to do so.
If it is impossible to make all the cities connected, print $−1$.

Samples

Input	Output
4 2 2 3 3 5	11
If we first do the road construction of the first kind to connect cities $0$ and $2$, then do it again to connect cities $1$ and $3$, and finally the road construction of the second kind to connect cities $1$ and $0$, all the cities will be connected together. The total cost incurred here is $3+3+5=11$ taka, which is the minimum possible.

Input	Output
6 1 3 4	-1
There is no way to make all the cities connected, so we should print $−1$.