#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
constexpr int INF = 1e9+100;
int dist[30030], visited[30030];
set<int> st[30030];
vector<int> a[30030];
struct Vertex{
int s, d, p;
Vertex(){}
Vertex(int _s, int _d, int _p): s(_s), d(_d), p(_p) {}
bool operator < (const Vertex &V) const{return d > V.d;}
};
int main(){
int n, m, s, e;
scanf("%d %d", &n, &m);
for (int i=1;i<=m;i++){
int x, p;
scanf("%d %d", &x, &p);
++x;
a[x].push_back(p);
if (i==1) s = x;
if (i==2) e = x;
}
fill(dist+1, dist+n+1, INF);
fill(visited+1, visited+n+1, 0);
dist[s] = 0;
for (int i=1;i<=n;i++){
sort(a[i].begin(), a[i].end());
a[i].erase(unique(a[i].begin(), a[i].end()), a[i].end());
}
priority_queue<Vertex> pq;
pq.emplace(s, 0, 0);
while(!pq.empty()){
auto [s, d, p] = pq.top(); pq.pop();
dist[s] = min(dist[s], d);
if (p){
if (st[s].find(p)!=st[s].end()) continue;
st[s].insert(p);
if (s-p > 0) pq.emplace(s-p, d+1, p);
if (s+p <= n) pq.emplace(s+p, d+1, p);
}
if (!visited[s]){
visited[s] = 1;
for (auto &p2:a[s]){
st[s].insert(p2);
if (s-p2 > 0) pq.emplace(s-p2, d+1, p2);
if (s+p2 <= n) pq.emplace(s+p2, d+1, p2);
}
}
}
/*for (int z=1;z<=n;z++){
int mn = INF, idx = -1;
for (int i=1;i<=n;i++) if (!visited[i] && mn > dist[i]){
mn = dist[i];
idx = i;
}
if (idx==-1) break;
visited[idx] = 1;
for (auto &p:a[idx]){
for (int i=idx-p, j=1;i>0;i-=p, j++) dist[i] = min(dist[i], dist[idx] + j);
for (int i=idx+p, j=1;i<=n;i+=p, j++) dist[i] = min(dist[i], dist[idx] + j);
}
}*/
if (dist[e]==INF) printf("-1\n");
else printf("%d\n", dist[e]);
return 0;
}
