#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;
void push ( int i , int j , int d ){
if( i < n && i >= 0 && !visited[i][P[j]])
q.push({i, j , d + 1 }) ;
}
int bfs()
{
int place, dog;
// q.push({B[0],0,0});
for (int v : here[B[0]])
{
push ( B[v] + P[v] , v , 0 ) ;
push ( B[v] - P[v] , v , 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];
push (plus , dog , d ) ;
push( minus , dog , d ) ;
for (int v : here[place])
{
push ( place + P[v] , v , d ) ;
push ( place - P[v] , 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;
}
