#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
using P = pair<int, int>;
using tp = tuple<int, int, int>;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;
const int inf = 1e9;
//const int NM
void solve() {
int n, m; cin >> n >> m;
int S = -1, E = -1;
set<P> s;
rep(i, 0, m) {
int x, y; cin >> x >> y;
if (i == 0)S = x;
if (i == 1)E = x;
s.insert(P(x, y));
}
m = sz(s);
vector<int> b(m), p(m), dist(n, inf);
auto it = s.begin();
rep(i, 0, m)
b[i] = it->first,
p[i] = it->second,
it++;
vector<P> light[n], heavy[n];
rep(i, 0, m)
if (p[i] > 173) {
int x = b[i]-p[i], y = 1;
while (0 <= x)
heavy[b[i]].push_back(P(x, y++)),
x -= p[i];
x = b[i]+p[i], y = 1;
while (x < n)
heavy[b[i]].push_back(P(x, y++)),
x += p[i];
} else {
if(b[i]+p[i] < n)light[b[i]].push_back(P(b[i]+p[i], p[i]));
if (0 <= b[i]-p[i])light[b[i]].push_back(P(b[i]-p[i], -p[i]));
}
priority_queue<tp, vector<tp>, greater<tp>> pq;
pq.push({0, S, 0}); dist[S] = 0;
while(!pq.empty()) {
auto [cost, nd, pw] = pq.top(); pq.pop();
if (pw == 0 && dist[nd] != cost)continue;
if (pw == 0) { // can use any edge
for (auto [ch, w]: heavy[nd])
if (cost+w < dist[ch])
dist[ch] = cost+w,
pq.push({dist[ch], ch, 0});
for (auto [ch, w]: light[nd])
pq.push({cost+1, ch, w});
} else { // can continue using light edge or stop
if (0 <= nd+pw && nd+pw < n) {
if(cost+1 < dist[nd+pw])
pq.push({cost+1, nd+pw, pw});
pq.push({cost+1, nd+pw, 0});
dist[nd+pw] = min(dist[nd+pw], cost+1);
}
}
}
cout << dist[E] << nl;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
