#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define fd(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se second
#define uint unsigned int
#define pb push_back
#define eb emplace_back
#define bit(s,i) ((s >> i) & 1)
#define off(s,i) (s & (~ (1 << i)))
#define ii pair <int , int>
#define iii1 pair <ii , int>
#define iii2 pair <int , ii>
#define TASK "SKY"
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int oo = 0x3f;
int n , m , p[30004] , b[30004];
vector < int > vc[30004];
int d[30004][104];
struct node {
int dis , i , p;
};
bool operator > (node a , node b) {
return a.dis > b.dis;
}
///--------------------------
void readf() {
cin >> n >> m;
}
///--------------------------
void solve() {
int sqr = 100;
for (int i = 0 ; i < m ; ++i) {
cin >> b[i] >> p[i];
vc[b[i]].pb(i);
}
int ans = 1e9;
memset(d,0x3f,sizeof(d));
priority_queue < node , vector < node > , greater < node > > wyna;
wyna.push({0 , b[0] , 0});
d[b[0]][0] = 0;
while (!wyna.empty()) {
node x = wyna.top();
int dis = x.dis , pk = x.p , i = x.i;
if (i == b[1]) ans = min(ans , dis);
wyna.pop();
if (dis != d[i][pk]) continue;
if (pk == 0) { // truong hop nhay den nha i lon hon can
for (auto x : vc[i])
if (p[x] <= sqr) { // buoc nhay con dog dang cho <= sqrt
if (d[i][p[x]] > dis) {
d[i][p[x]] = dis;
wyna.push({dis , i , p[x]});
}
} else { // con dog dang dung lai tai nha i
int pp = p[x];
int cnt = 0;
for (int x = i ; x < n ; x += pp) { // cho con cho den i + x * p va dung lai
if (d[x][0] > dis + cnt) {
d[x][0] = dis + cnt;
wyna.push({dis + cnt , x , 0});
}
cnt++;
}
cnt = 0;
for (int x = i ; x >= 0 ; x -= pp) { // cho con cho den i + x * p va dung lai
if (d[x][0] > dis + cnt) {
d[x][0] = dis + cnt;
wyna.push({dis + cnt , x , 0});
}
cnt++;
}
}
} else { // truong hop nhay den nha i <= sqrt va di tiep
if (i + pk < n && d[i + pk][pk] > dis + 1) { // di tiep sang ben trai
d[i + pk][pk] = dis + 1;
wyna.push({dis + 1 , i + pk , pk});
}
if (i - pk >= 0 && d[i - pk][pk] > dis + 1) { // di tiep sang ben phai
d[i - pk][pk] = dis + 1;
wyna.push({dis + 1 , i - pk , pk});
}
if (d[i][0] > dis) { // con dog hien tai dung lai
d[i][0] = dis;
wyna.push({dis , i , 0});
}
}
}
if (ans == 1e9) cout << -1;
else cout << ans;
}
///--------------------------
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
readf();
solve();
}
