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