#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 3e4 + 10, M = 5e6, INF = 1e9;
map<pii, int> d;
vector<int> t[N];
bool vis[N];
deque<pii> q;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m;
int sp, sb, se;
for(int i=0; i<m; i++){
int p, b; cin >> p >> b;
t[p].pb(b);
if(i == 0)
sp = p, sb = b;
if(i == 1)
se = p;
}
q.push_back({sp, sb});
d[{sp, sb}] = 0;
while(!q.empty()){
int p = q.front().F, b = q.front().S;
int dis = d[{p, b}];
q.pop_front();
if(!vis[p]){
for(auto l : t[p]){
if(d.count({p, l}) == 0)
d[{p, l}] = dis, q.push_front({p, l});
}
vis[p] = true;
}
if(p + b < n){
if(d.count({p + b, b}) == 0)
d[{p + b, b}] = dis + 1, q.push_back({p + b, b});
}
if(p - b >= 0){
if(d.count({p - b, b}) == 0)
d[{p - b, b}] = dis + 1, q.push_back({p - b, b});
}
}
int mn = INF;
for(int i=0; i<=n; i++){
if(d.count({se, i}))
mn = min(mn, d[{se, i}]);
}
if(mn < INF)
cout << mn << endl;
else cout << -1 << endl;
}
