// Need to git gud and reach 1900+
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define prev prev123
#define next next123
#define pow pow123
#define left left123
#define right right123
const int N = 30007;
const int M = 207;
const int INF = 1e9 + 7;
int a[N], b[N];
int d[N][M];
int m, n, s, f;
vector < int > lst[N];
main(){ // If you don't know what to do, check the text box at the bottom
cin >> m >> n;
for (int i = 1; i <= n; i++){
scanf("%d%d", &a[i], &b[i]);
lst[a[i] + 1].pb(b[i]);
}
s = a[1] + 1, f = a[2] + 1;
priority_queue < pair < int, pi > > pq;
pq.push(mk(0, mk(s, 0)));
memset(d, 0x3f3f3f3f, sizeof(d));
d[s][0] = 0;
while (!pq.empty()){
int w = -pq.top().fr, v = pq.top().sc.fr, pw = pq.top().sc.sc;
pq.pop();
if (d[v][pw] < w)
continue;
if (pw == 0){
for (int to : lst[v]){
if (to > 173){
int pos = v, c = 0;
while (pos + to <= m){
pos += to; c++;
if (d[pos][0] > d[v][0] + c){
d[pos][0] = d[v][0] + c;
pq.push(mk(-d[pos][0], mk(pos, 0)));
}
}
pos = v, c = 0;
while (pos - to > 0){
pos -= to; c++;
if (d[pos][0] > d[v][0] + c){
d[pos][0] = d[v][0] + c;
pq.push(mk(-d[pos][0], mk(pos, 0)));
}
}
}
else {
if (d[v][to] > d[v][0]){
d[v][to] = d[v][0];
pq.push(mk(-d[v][to], mk(v, to)));
}
}
}
}
else {
if (v + pw <= m && d[v + pw][pw] > d[v][pw] + 1){
d[v + pw][pw] = d[v][pw] + 1;
pq.push(mk(-d[v + pw][pw], mk(v + pw, pw)));
}
if (v + pw <= m && d[v + pw][0] > d[v][pw] + 1){
d[v + pw][0] = d[v][pw] + 1;
pq.push(mk(-d[v + pw][0], mk(v + pw, 0)));
}
if (v - pw > 0 && d[v - pw][pw] > d[v][pw] + 1){
d[v - pw][pw] = d[v][pw] + 1;
pq.push(mk(-d[v - pw][pw], mk(v - pw, pw)));
}
if (v - pw > 0 && d[v - pw][0] > d[v][pw] + 1){
d[v - pw][0] = d[v][pw] + 1;
pq.push(mk(-d[v - pw][0], mk(v - pw, 0)));
}
}
}
if (d[f][0] != d[0][0])
printf("%d", d[f][0]);
else
puts("-1");
}
/*
Totally not inspired by BenQ's template
Things you should do:
1. Look for stupid typos in code e.g 1 instead of -1 etc
2. Check if there is no infinite loops
3. "Measure twice, cut once"
4. Stay focused
*/
