0012 - Jakarta Skyscrapers

課題(Description)

ジャカルタには一直線上に建てられた N 個の超高層ビルがある．ビルには左から右の順に，0 から N − 1 までの番号が付けられている．ジャカルタにはこれら以外の超高層ビルはない．

ジャカルタには ドージ (doge) と呼ばれる神秘的な生き物が M 匹生息している．ドージには 0 から M − 1 までの番号が付けられている．最初，ドージ i は超高層ビル B_i にいる．ドージ i は神秘的な力を持っており，その力は正整数 P_i で表される．神秘的な力を使って，ドージは超高層ビルの間をジャンプすることができる．神秘的な力 p を持つドージの現在位置が超高層ビル b のとき，1 回のジャンプによって，そのドージは超高層ビル b + p (0 ≤ b + p < N のとき)，または，超高層ビル b − p (0 ≤ b − p < N のとき) のいずれかへ移動することができる．

ドージ 0 は最高位のドージであり，すべてのドージのリーダーである．ドージ 0 は，ドージ 1 に伝えるべき緊急のニュースを持っている．できるだけ早くそのニュースをドージ 1 に伝えたい．ニュースを受け取ったドージのみが，次のいずれかの行動をとることができる．

もし，ニュースをドージ 1 に伝えることが可能な場合は，そのために必要な全ドージのジャンプの合計回数の最小値を求めることで，ドージたちを助けてほしい．

入力形式(Input Format)

1 行目には，整数 N, M が書かれている．続く M 行のうちのそれぞれには，2 つの整数 B_i, P_i が書かれている．

出力形式(Ouput Format)

ジャンプの合計回数の最小値を 1 行で出力せよ．もし，ニュースをドージ 1 に伝えることが不可能な場合は -1 を出力せよ．

入力例(Sample Input)

5 3
0 2
1 1
4 1

出力例(Sample Output)

5

解説(Explanation)

5 回のジャンプによってニュースを伝えるには，次のように行動すればよい．

小課題(Subtasks)

すべての入力データは以下の条件を満たす.

小課題 1 (Subtask 1) [10 点]

• 1 ≤ N ≤ 10
• 1 ≤ P_i ≤ 10
• 2 ≤ M ≤ 3

小課題 2 (Subtask 2) [12 点]

• 1 ≤ N ≤ 100
• 1 ≤ P_i ≤ 200
• 2 ≤ M ≤ 2,000

小課題 3 (Subtask 3) [14 点]

• 1 ≤ N ≤ 2,000
• 1 ≤ P_i ≤ 2,000
• 2 ≤ M ≤ 2,000

小課題 4 (Subtask 4) [21 点]

• 1 ≤ N ≤ 2,000
• 1 ≤ P_i ≤ 2,000
• 2 ≤ M ≤ 30,000

小課題 5 (Subtask 5) [43 点]

• 1 ≤ N ≤ 30,000
• 1 ≤ P_i ≤ 30,000
• 2 ≤ M ≤ 30,000