#pragma GCC optimize("O3")
#pragma GCC target("sse2,sse3,ssse3,sse4,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)
#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second
const int BIG = 2*(int)(1e9);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
void solve();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
const int borneSuj = 30*1000 + 5;
const int borneTab = 200*borneSuj;
int gt[borneSuj][200];
int inv[borneTab];
bool witPrev[borneTab];
bool witSuiv[borneTab];
int arr = -1, dep=-1;
int nbPlaces, nbDoges, nbNoeuds;
int limSqd;
vector<int> doge[borneSuj];
void solve()
{
cin >> nbPlaces >> nbDoges;
chmax(nbPlaces, 20);
nbNoeuds = nbPlaces;
limSqd = sqrt(nbPlaces);
form2(distance, 1, limSqd) {
form(ini, distance) {
for (int place = ini; place < nbPlaces; place += distance) {
int corNod = nbNoeuds; ++nbNoeuds;
inv[corNod] = place+1;
gt[place][distance] = corNod;
if (place != ini) {
witPrev[corNod] = true;
witSuiv[corNod-1] = true;
}
}
}
}
form(iDoge, nbDoges) {
int pos, saut;
cin >> pos >> saut;
if (iDoge == 0) dep = pos;
if (iDoge == 1) arr = pos;
doge[pos].push_back(saut);
}
vector<int> md(nbNoeuds, BIG);
vector<int> etat(nbNoeuds, 2);
deque<int> m1;
m1.push_front(dep);
md[dep] = 0;
while (! m1.empty()) {
int nod = m1.front(); m1.pop_front();
etat[nod] = 0;
int dis = md[nod];
auto propag = [&] (int vo, int poids) {
if (etat[vo] == 2) {
m1.push_back(vo);
etat[vo] = 1;
md[vo] = dis + poids;
} else if (etat[vo] == 1) {
chmin(md[vo], dis + poids);
} else {
if (dis+poids < md[vo]) {
md[vo] = dis+poids;
etat[vo] = 1;
m1.push_back(vo);
}
}
};
if (nod < nbPlaces) {
int pos = nod;
for (int saut : doge[nod]) {
if (saut < limSqd) {
propag(gt[pos][saut], 0);
} else {
for (int dd = 1; pos + dd*saut < nbPlaces; ++dd) {
propag(pos+dd*saut, dd);
}
for (int dd = 1; pos - dd*saut >= 0; ++dd) {
propag(pos-dd*saut, dd);
}
}
}
}
if (nod >= nbPlaces) {
if (inv[nod]) propag(inv[nod]-1, 0);
if (witPrev[nod]) propag(nod-1, 1);
if (witSuiv[nod]) propag(nod+1, 1);
}
}
if (md[arr] == BIG) cout << "-1\n";
else cout << md[arr] << "\n";
}
