#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 ;
vpi here [N] ;
bool visited[ N ][ N ] ;
int solve (){
queue<pi> q ;
int place , dog ;
q.push({B[0],0}) ;
while ( !q.empty() ){
place = q.front().fi ;
dog = q.front().se ;
q.pop();
if( place == B[1] ){
return dist[1] ;
}
// cerr << place << " " << dog << " " << dist[place] << endl;
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 } ) , dist[plus] = dist[place]+1 ;
if( minus >= 0 && !visited[minus][P[dog]])
q.push( { minus , dog } ) , dist[minus] = dist[place] + 1 ;
for( pi v : here[place] ){
// cout << v.fi << " " << v.se << endl;
if( !visited[v.fi][P[v.se]] )
q.push( {v.fi , v.se } ) ;
}
}
return -1 ;
}
void input(){
// ifstream cin ("in.in") ;
cin >> n >> m ;
for(int i = 0 ; i < m ; i++ ){
cin >> B[i] >> P[i] ;
if(i)here[B[i]].pb({B[i] , i}) ;
}
}
int main(){
input() ;
cout << solve ( ) << endl;
}
