#include <bits/stdc++.h>
using namespace std;
/// 12:08
const int Nmax = 30005;
const int base = 30007;
typedef pair<int,int> Pair;
vector<int> v[Nmax];
vector<Pair> edge[Nmax];
int salt[Nmax], pos[Nmax], dist[Nmax], last[Nmax];
int n, m;
int solve(int start, int finish)
{
priority_queue< Pair, vector<Pair>, greater<Pair> > heap;
heap.push({0, start});
int i;
for(i=0; i<n; ++i) dist[i] = 1e9;
dist[start] = 0;
while(heap.size())
{
int node, dst;
tie(dst, node) = heap.top();
heap.pop();
if(dist[node] != dst) continue;
if(node == finish) return dst;
for(auto &it : edge[node])
if(dist[node] + it.second < dist[it.first])
{
dist[it.first] = dist[node] + it.second;
heap.push({dist[it.first], it.first});
}
}
return -1;
}
int main()
{
// freopen("input", "r", stdin);
cin.sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
int i;
for(i=0; i<m; ++i)
{
cin >> pos[i] >> salt[i];
v[salt[i]].push_back(pos[i]);
}
for(i=0; i<n; ++i)
{
sort(v[i].begin(), v[i].end());
v[i].erase( unique(v[i].begin(), v[i].end()) , v[i].end() );
}
for(i=1; i<=30000; ++i)
{
for(auto it : v[i]) last[it] = i;
for(auto it : v[i])
{
int p, dst;
for(p = it - i, dst = 1; p >= 0; p -= i, ++dst)
{
edge[it].push_back({p, dst});
if(last[p] == i) break;
}
for(p = it + i, dst = 1; p<n; p += i, ++dst)
{
edge[it].push_back({p, dst});
if(last[p] == i) break;
}
}
}
cout << solve(pos[0], pos[1]) << '\n';
return 0;
}
