#include <bits/stdc++.h>
#define ii pair <int, int>
#define iii pair <ii, int>
#define fi first.first
#define se first.second
#define th second
using namespace std;
#define task "code"
#define all(s) s.begin(), s.end()
typedef long long ll;
const int ar = 3e5+2;
const ll mod = 998244353;
const int oo = 1e9;
const int LG = 9;
const int BLOCK = 100;
int n, m, b[ar], p[ar], d[ar][BLOCK + 1];
priority_queue <iii, vector <iii>, greater <iii>> q;
vector <int> pos[ar];
void dijkstra() {
q.push({{0, b[0]}, 0});
int ans = 1e9;
memset(d, 0x3f, sizeof d);
d[b[0]][0] = 0;
while (!q.empty()) {
iii x = q.top();
int dis = x.fi , pk = x.th , i = x.se;
if (i == b[1]) ans = min(ans , dis);
q.pop();
if (dis != d[i][pk]) continue;
if (pk == 0) {
for (auto x : pos[i])
if (p[x] <= BLOCK) {
if (d[i][p[x]] > dis) {
d[i][p[x]] = dis;
q.push({{dis , i} , p[x]});
}
} else {
int pp = p[x];
int cnt = 0;
for (int x = i ; x < n ; x += pp) {
if (d[x][0] > dis + cnt) {
d[x][0] = dis + cnt;
q.push({{dis + cnt , x} , 0});
}
cnt++;
}
cnt = 0;
for (int x = i ; x >= 0 ; x -= pp) {
if (d[x][0] > dis + cnt) {
d[x][0] = dis + cnt;
q.push({{dis + cnt , x} , 0});
}
cnt++;
}
}
} else {
if (i + pk < n && d[i + pk][pk] > dis + 1) {
d[i + pk][pk] = dis + 1;
q.push({{dis + 1 , i + pk} , pk});
}
if (i - pk >= 0 && d[i - pk][pk] > dis + 1) {
d[i - pk][pk] = dis + 1;
q.push({{dis + 1 , i - pk} , pk});
}
if (d[i][0] > dis) {
d[i][0] = dis;
q.push({{dis , i} , 0});
}
}
}
if (ans == 1e9) cout << -1;
else cout << ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin >> n >> m;
for(int i = 0; i < m; ++i)
cin >> b[i] >> p[i], pos[b[i]].push_back(i);
dijkstra();
return 0;
}
