// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
void fast_io() {
// freopen("", "r", stdin);
// freopen("", "w", stdout);
ios::sync_with_stdio(0);
cin.tie();
cout.tie();
cout << setprecision(9);
}
#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int N = 3e4 + 5;
vector<int> adj[N];
int dist[N];
void solve() {
int n, m; cin >> n >> m;
int pos[m + 1] = {}, val[m + 1] = {};
vector<int> avl[n];
for (int i = 0; i < m; i++){
int b, p; cin >> b >> p;
pos[i] = b;
val[i] = p;
avl[b].push_back(i);
}
for (int i = 0; i < n; i++) dist[i] = 1e18;
dist[pos[0]] = 0;
map<pair<int, int>, bool> c;
queue<vector<int>> q;
bool vis[n] = {};
for (auto i : avl[pos[0]]){
q.push({pos[i], val[i], 0});
}
while (q.size()){
vector<int> A = q.front();
q.pop();
int Pos = A[0], power = A[1], Dist = A[2];
// cout << Pos << ' ' << power << ' ' << Dist << endl;
// if (power == 1 && Pos == 4) cout << c[{4, 1}] << endl;
dist[Pos] = min(Dist, dist[Pos]);
if (Pos + power < n && !c[{Pos + power, power}]){
c[{Pos + power, power}] = 1;
q.push({Pos + power, power, Dist + 1});
if (!vis[Pos + power]){
// if (Pos + power == 4) cout << Dist + 1 << endl;
vis[Pos + power] = 1;
for (auto i : avl[Pos + power]){
q.push({pos[i], val[i], min(dist[pos[i]], Dist + 1)});
}}
}
// if (Pos == 3 && power == 1) cout << "Here" << endl;
if (Pos - power >= 0 && !c[{Pos - power, power}]){
c[{Pos - power, power}] = 1;
q.push({Pos - power, power, Dist + 1});
if (vis[Pos - power]){
vis[Pos - power] = 1;
for (auto i : avl[Pos - power]){
q.push({pos[i], val[i], min(dist[pos[i]], Dist + 1)});
}}
}
}
cout << dist[pos[1]] << endl;
}
signed main() {
fast_io();
srand(chrono::steady_clock::now().time_since_epoch().count());
int tc = 1;
// cin >> tc;
while (tc--) solve();
return 0;
}
