Limits 1s, 1.0 GB

There are NN cities and initially 00 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 00 to N1N - 1. There are MM types of road constructions which can be performed among these cities. For each k=1,2,3,,Mk = 1, 2, 3, …, M, the kk-th kind of road construction is to choose an integer xx such that 0x<N0 \le x < N and construct a new two-way road connecting city xx and city (x+Ak) mod N(x + A_k)\text{ mod } N. Performing the kk-th kind of road construction once costs CkC_k taka.

You can do these MM 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:

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

Input

Input is given from Standard Input in the following format:

N MA1 C1A2 C2AM CMN\ 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−1.

Samples

InputOutput
4 2
2 3
3 5
11

If we first do the road construction of the first kind to connect cities 00 and 22, then do it again to connect cities 11 and 33, and finally the road construction of the second kind to connect cities 11 and 00, all the cities will be connected together. The total cost incurred here is 3+3+5=113+3+5=11 taka, which is the minimum possible.

InputOutput
6 1
3 4
-1

There is no way to make all the cities connected, so we should print 1−1.


Submit

Login to submit.

Statistics

61% Solution Ratio
ApuOrghoEarliest, 8M ago
The_crawlerFastest, 0.0s
ir.rafioLightest, 5.5 MB
Iztihad.9888Shortest, 463B
Toph uses cookies. By continuing you agree to our Cookie Policy.