#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
using ll = long long;
const int MAX = 3e4;
const int SQRT = 200;
int nbSauts[MAX][SQRT+1];
struct Situation
{
int building, power, sauts;
bool operator<(Situation other) const
{
return sauts > other.sauts;
}
};
int main(void)
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int nbBat, nbDog;
cin >> nbBat >> nbDog;
vector<pair<int, int> > dogs(nbDog);
vector<int> dogsInBat[MAX];
for (auto &[bat, pow] : dogs)
{
cin >> bat >> pow;
dogsInBat[bat].push_back(pow);
}
for (int i(0); i < nbBat; ++i)
for (int j(0); j <= SQRT; ++j)
nbSauts[i][j] = 1e9;
nbSauts[dogs[0].first][SQRT] = 0;
priority_queue<Situation> q;
q.push({dogs[0].first, SQRT, 0});
while (SZ(q))
{
auto situ = q.top(); q.pop();
if (situ.building == dogs[1].first)
{
cout << situ.sauts << endl;
return 0;
}
if (situ.sauts > nbSauts[situ.building][situ.power])
continue ;
for (auto p : dogsInBat[situ.building])
{
if (p < SQRT)
{
if (situ.building - p >= 0 and nbSauts[situ.building-p][p] > situ.sauts+1)
{
q.push({situ.building-p, p, situ.sauts+1});
nbSauts[situ.building-p][p] = situ.sauts + 1;
}
if (situ.building+p < nbBat and nbSauts[situ.building+p][p]>situ.sauts+1)
{
q.push({situ.building+p, p, situ.sauts+1});
nbSauts[situ.building+p][p] = situ.sauts + 1;
}
}
else
{
for (int i(1); p * i + situ.building < nbBat; ++i)
{
if (nbSauts[situ.building+i*p][SQRT] > situ.sauts+i)
{
q.push({situ.building+i*p, SQRT, situ.sauts + i});
nbSauts[situ.building+i*p][SQRT] = situ.sauts + i;
}
}
for (int i(-1); p*i + situ.building >= 0; --i)
{
if (nbSauts[situ.building+i*p][SQRT] > situ.sauts-i)
{
q.push({situ.building+i*p, SQRT, situ.sauts - i});
nbSauts[situ.building+i*p][SQRT] = situ.sauts -i;
}
}
}
}
if (situ.power < SQRT)
{
int p = situ.power;
if (situ.building - p >= 0 and nbSauts[situ.building-p][p] > situ.sauts+1)
{
q.push({situ.building-p, p, situ.sauts+1});
nbSauts[situ.building-p][p] = situ.sauts + 1;
}
if (situ.building+p < nbBat and nbSauts[situ.building+p][p] > situ.sauts+1)
{
q.push({situ.building+p, p,situ.sauts+1});
nbSauts[situ.building+p][p] = situ.sauts + 1;
}
}
}
cout << -1 << endl;
}
