#include <bits/stdc++.h>
using namespace std;
/// 12:08
const int Nmax = 30005;
const int base = 30007;
vector<int> v[Nmax];
int salt[Nmax], pos[Nmax];
bool reached[Nmax];
int n, m;
unordered_map<int, int> dist;
queue< int > q;
static int code(int x, int y)
{
return x * base + y;
}
static pair<int,int> decode(int x)
{
return {x / base, x % base};
}
static void baga(int x, int curr)
{
reached[x] = 1;
for(auto it : v[x])
if(!dist[code(x, it)])
{
dist[code(x, it)] = curr + 1;
q.push(code(x, it));
}
}
static int solve()
{
if(pos[0] == pos[1]) return 0;
baga(pos[0], 0);
while(q.size())
{
int x, s;
tie(x, s) = decode(q.front());
q.pop();
int curr = dist[code(x, s)];
if(x + s < n && !dist[code(x + s, s)])
{
dist[code(x + s, s)] = curr + 1;
q.push(code(x+s, s));
if(x + s == pos[1]) return curr;
if(!reached[x+s]) baga(x+s, curr);
}
if(x - s >= 0 && !dist[code(x - s, s)])
{
dist[code(x - s, s)] = curr + 1;
q.push(code(x-s, s));
if(x - s == pos[1]) return curr;
if(!reached[x-s]) baga(x-s, curr);
}
}
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[pos[i]].push_back(salt[i]);
}
cout << solve() << '\n';
return 0;
}
