#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
const int maxn = 30010;
const int INF = INT_MAX/2;
typedef pair<int, pi> pp;
int n,doges;
vector <int> bufflist[maxn];
vector <int> smalldogs[maxn];
const int len = 174;
int dist[maxn][len+10];
int stp,endp;
int32_t main() {
FAST
cin >> n >> doges;
for (int i =0;i<doges;i++) {
int pos, jump; cin >> pos >> jump;
if (i == 0) stp = pos;
if (i == 1) endp = pos;
if (jump < len) {
smalldogs[pos].push_back(jump);
} else {
bufflist[pos].push_back(jump);
}
}
memset(dist, -1, sizeof dist);
deque <pp> pq;
pq.push_front(pp(0,pi(stp,0)));
dist[stp][0] = 0;
while (!pq.empty()) {
pp cur = pq.front(); pq.pop_front();
int d = cur.f, pos = cur.s.f, jump = cur.s.s;
//cout << pos << " " << jump << " " << d << "\n";
if (jump == 0) {
if (d != dist[pos][0]) continue;
for (auto i: bufflist[pos]) {
if (pos + i < n) pq.push_back(pp(d+1,pi(pos + i,i)));
if (pos - i >= 0) pq.push_back(pp(d+1,pi(pos - i,-i)));
}
for (auto i: smalldogs[pos]) {
if (dist[pos][i] == -1 or dist[pos][i] > d) {
dist[pos][i] = d;
pq.push_front(pp(d, pi(pos,i)));
}
}
} else if (jump > 0 and jump < len) {
if (d != dist[pos][jump]) continue;
if (dist[pos][0] == -1 or dist[pos][0] > d) {
dist[pos][0] = d;
pq.push_front(pp(d,pi(pos,0)));
}
int newp = pos + jump;
if (newp < n) {
if (dist[newp][jump] == -1 or dist[newp][jump] > d + 1) {
dist[newp][jump] = d + 1;
pq.push_back(pp(d+1, pi(newp,jump)));
}
}
newp = pos - jump;
if (newp >= 0) {
if (dist[newp][jump] == -1 or dist[newp][jump] > d + 1) {
dist[newp][jump] = d + 1;
pq.push_back(pp(d + 1, pi(newp,jump)));
}
}
} else { //On a buff dog train
//Get off
if (dist[pos][0] == -1 or dist[pos][0] > d) {
dist[pos][0] = d;
pq.push_front(pp(d,pi(pos,0)));
}
//Continue train
if (jump > 0 and pos + jump < n) pq.push_back(pp(d+1,pi(pos + jump,jump)));
else if (jump < 0 and pos + jump >= 0) pq.push_back(pp(d+1,pi(pos + jump,jump)));
}
}
cout << dist[endp][0];
}
