#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define allarr(a) a, a + n
#define ll long long
#define ull unsigned long long
#define pb push_back
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<int, pi> trp;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
ll ab(ll x) { return (x > 0 ? x : -x); }
const int N = 3005;
int P[N], B[N];
int dist[N], n, m;
vector<int> here[N];
bool visited[N][N];
queue<vector<int>> q;
int bfs()
{
int place, dog;
q.push({B[0],0,0});
while (!q.empty())
{
place = q.front()[0];
dog = q.front()[1];
int d = q.front()[2] ;
q.pop();
if (place == B[1])
{
return d ;
}
visited[place][P[dog]] = 1;
int plus = place + P[dog], minus = place - P[dog];
if (plus < n && !visited[plus][P[dog]])
q.push({plus, dog , d + 1 }) ;
if (minus >= 0 && !visited[minus][P[dog]])
q.push({minus, dog , d + 1 }) ;
for (int v : here[place])
{
if( !visited[place][P[v]])
q.push( {place , v , d } ) ;
}
}
return -1;
}
void input()
{
// ifstream cin ("in.in") ;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> B[i] >> P[i];
here[B[i]].pb(i);
}
}
int main()
{
input();
cout << bfs() << endl;
}
