#include <bits/stdc++.h>
using namespace std;
pair <int , int> sir[30001];
int distanta[30001];
bool vizitat[30001];
int main ()
{
ios :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int numar_noduri_1 , numar_noduri_2;
cin >> numar_noduri_1 >> numar_noduri_2;
for (int indice = 1 ; indice <= numar_noduri_1 ; indice++)
{ distanta[indice] = INT32_MAX; }
for (int indice = 1 ; indice <= numar_noduri_2 ; indice++)
{ cin >> sir[indice].first >> sir[indice].second; sir[indice].first++; }
distanta[sir[1].first] = 0;
while (true)
{
int inceput = -1;
for (int indice = 1 ; indice <= numar_noduri_2 ; indice++) {
if (!vizitat[indice] && (inceput == -1 || distanta[sir[inceput].first] > distanta[sir[indice].first]))
{ inceput = indice; }
}
if (distanta[inceput] == INT32_MAX)
{ cout << "-1"; break; }
if (inceput == 2)
{ cout << distanta[sir[2].first]; break; }
vizitat[inceput] = true;
for (int indice = sir[inceput].first ; indice <= numar_noduri_1 ; indice += sir[inceput].second)
{ distanta[indice] = min(distanta[indice] , distanta[sir[inceput].first] + (indice - sir[inceput].first) / sir[inceput].second); }
for (int indice = sir[inceput].first - sir[inceput].second ; indice > 0 ; indice -= sir[inceput].second)
{ distanta[indice] = min(distanta[indice] , distanta[sir[inceput].first] + (sir[inceput].first - indice) / sir[inceput].second); }
}
return 0;
}
