#include <bits/stdc++.h>
using namespace std;
vector < pair <int , int> > adiacenta[60001];
int distanta[60001];
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_2 ; indice++)
{
int inceput , termen;
cin >> inceput >> termen;
inceput++;
for (int nod = inceput ; nod <= numar_noduri_1 ; nod += termen)
{ adiacenta[indice + numar_noduri_1].emplace_back(nod , (nod - inceput) / termen); }
for (int nod = inceput - termen ; nod > 0 ; nod -= termen)
{ adiacenta[indice + numar_noduri_1].emplace_back(nod , (inceput - nod) / termen); }
adiacenta[inceput].emplace_back(indice + numar_noduri_1 , 0);
}
for (int indice = 1 ; indice <= numar_noduri_1 + numar_noduri_2 ; indice++)
{ distanta[indice] = INT32_MAX; }
priority_queue < pair <int , int> > candidati;
candidati.emplace(distanta[numar_noduri_1 + 1] = 0 , numar_noduri_1 + 1);
while (!candidati.empty())
{
const int nod = candidati.top().second;
if (distanta[nod] != -candidati.top().first)
{ candidati.pop(); continue; }
candidati.pop();
for (auto& vecin : adiacenta[nod]) {
if (distanta[vecin.first] > distanta[nod] + vecin.second)
{ candidati.emplace(-(distanta[vecin.first] = distanta[nod] + vecin.second) , vecin.first); }
}
}
cout << (distanta[numar_noduri_1 + 2] == INT32_MAX ? -1 : distanta[numar_noduri_1 + 2]);
return 0;
}
