J - Traveling Stall Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君はお祭りに来ています。会場には N 個の区画が一列に並んでおり、左から順に区画 1, 区画 2, \ldots, 区画 N と番号が付いています。高橋君は区画の列の端を越えて反対側に移動することはできません。すなわち、区画 1 からさらに左へ移動したり、区画 N からさらに右へ移動したりすることはできません。

このお祭りには M 台の移動式の屋台が出店しています。i 番目の屋台は初期位置 S_i と移動量 D_i をもちます。まだ買い物をしていない屋台 i は、時刻 t（t = 0, 1, 2, \ldots）において区画 ((S_i + t \cdot D_i - 1) \bmod N) + 1 に位置します。ここで a \bmod N は a を N で割った非負の余りを表します。すなわち、屋台は時刻が 1 進むごとに区画番号が D_i だけ巡回的に増加します（区画 N の次は区画 1 に戻ります）。D_i = 0 の場合は常に区画 S_i に留まります。同じ区画に複数の屋台が同時に存在することもあります。

高橋君は時刻 0 に区画 1 にいます。時刻 1, 2, 3, \ldots のそれぞれにおいて、以下の手順がこの順番で行われます。時刻 0 では以下の手順は行われません（時刻 0 の時点で高橋君と同じ区画に屋台がいても買い物はできません）。

  1. 高橋君の移動: 高橋君は次のいずれか 1 つを行います。
  • 現在いる区画に留まる。
  • 隣接する区画に移動する。すなわち、現在区画 p（2 \leq p \leq N-1）にいるとき区画 p-1 または区画 p+1 に、区画 1 にいるとき区画 2 に、区画 N にいるとき区画 N-1 に移動できます。
  1. 屋台の移動: まだ買い物をしていない各屋台が、上記の位置の式に従い時刻 t における区画に移動します。
  2. 買い物: 高橋君と同じ区画にいる、まだ買い物をしていない屋台のすべてについて買い物が行われます。一部の屋台だけ買い物をしないという選択はできません。買い物済みの屋台は以降の手順に影響しません（移動せず、高橋君の移動も妨げません）。

高橋君はすべての屋台で買い物をしたいです。すべての屋台での買い物を完了できる最小の時刻を求めてください。すべての屋台での買い物を完了することが不可能な場合は -1 を出力してください。

制約

  • 1 \leq N \leq 100
  • 1 \leq M \leq 10
  • 1 \leq S_i \leq N
  • 0 \leq D_i \leq N - 1
  • 入力はすべて整数である

入力

N M
S_1 D_1
S_2 D_2
\vdots
S_M D_M
  • 1 行目には、区画の数 N と屋台の数 M がスペース区切りで与えられる。
  • 続く M 行のうち i 行目には、i 番目の屋台の初期位置 S_i と移動量 D_i がスペース区切りで与えられる。

出力

すべての屋台で買い物を完了できる最小の時刻を 1 行で出力せよ。不可能な場合は -1 を出力せよ。

入力例 1

5 2
3 0
1 1

出力例 1

2

入力例 2

4 3
1 0
4 0
2 2

出力例 2

4

入力例 3

12 5
2 3
7 0
11 5
4 8
9 6

出力例 3

9

入力例 4

100 10
1 0
100 99
50 25
73 37
12 64
88 10
34 51
65 0
27 83
91 42

出力例 4

77

入力例 5

1 1
1 0

出力例 5

1

Score : 433 pts

Problem Statement

Takahashi is at a festival. The venue has N sections arranged in a row, numbered section 1, section 2, \ldots, section N from left to right. Takahashi cannot move beyond the ends of the row of sections. That is, he cannot move further left from section 1 or further right from section N.

There are M mobile stalls at this festival. The i-th stall has an initial position S_i and a movement amount D_i. A stall i that has not yet been shopped at is located at section ((S_i + t \cdot D_i - 1) \bmod N) + 1 at time t (t = 0, 1, 2, \ldots). Here, a \bmod N denotes the non-negative remainder when a is divided by N. In other words, the stall's section number increases cyclically by D_i with each unit of time (after section N, it returns to section 1). If D_i = 0, the stall always stays at section S_i. Multiple stalls may exist at the same section simultaneously.

Takahashi is at section 1 at time 0. At each of times 1, 2, 3, \ldots, the following steps are performed in this order. These steps are NOT performed at time 0 (even if a stall is at the same section as Takahashi at time 0, he cannot shop there).

  1. Takahashi's movement: Takahashi performs exactly one of the following:
  • Stay at the current section.
  • Move to an adjacent section. Specifically, if he is currently at section p (2 \leq p \leq N-1), he can move to section p-1 or section p+1; if at section 1, he can move to section 2; if at section N, he can move to section N-1.
  1. Stall movement: Each stall that has not yet been shopped at moves to its section at time t according to the position formula above.
  2. Shopping: Shopping is performed at all stalls that have not yet been shopped at and are at the same section as Takahashi. It is not possible to choose to skip shopping at only some of the stalls. Stalls that have already been shopped at do not affect subsequent steps (they do not move and do not obstruct Takahashi's movement).

Takahashi wants to shop at all stalls. Find the minimum time at which shopping at all stalls can be completed. If it is impossible to complete shopping at all stalls, output -1.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq M \leq 10
  • 1 \leq S_i \leq N
  • 0 \leq D_i \leq N - 1
  • All inputs are integers

Input

N M
S_1 D_1
S_2 D_2
\vdots
S_M D_M
  • The first line contains the number of sections N and the number of stalls M, separated by a space.
  • The i-th of the following M lines contains the initial position S_i and movement amount D_i of the i-th stall, separated by a space.

Output

Output in one line the minimum time at which shopping at all stalls can be completed. If it is impossible, output -1.

Sample Input 1

5 2
3 0
1 1

Sample Output 1

2

Sample Input 2

4 3
1 0
4 0
2 2

Sample Output 2

4

Sample Input 3

12 5
2 3
7 0
11 5
4 8
9 6

Sample Output 3

9

Sample Input 4

100 10
1 0
100 99
50 25
73 37
12 64
88 10
34 51
65 0
27 83
91 42

Sample Output 4

77

Sample Input 5

1 1
1 0

Sample Output 5

1