#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 ] ;
queue<pi> q ;
void solve(int place , int dog ){
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;
}
int bfs (){
int place , dog ;
for(pi v : here[B[0]]){
q.push( {v.fi, v.se } ) ;
}
while ( !q.empty() ){
place = q.front().fi ;
dog = q.front().se ;
q.pop();
if( place == B[1] ){
return dist[place] ;
}
solve (place , dog ) ;
// cerr << place << " " << dog << " " << dist[place] << endl;
for( pi v : here[place] ){
solve ( 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] ;
here[B[i]].pb({B[i] , i}) ;
}
}
int main(){
input() ;
cout << bfs ( ) << endl;
}
