#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int mxN = 30001;
ttgl arr[mxN];
set<int> st[mxN];
vector<ttgl> adj[mxN];
int dist[mxN];
int n, m;
int main()
{
//freopen("filename.in", "r", stdin);
//freopen("filename.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m;
owo(i, 0, m) {
cin>>arr[i].first>>arr[i].second;
st[arr[i].first].insert(arr[i].second);
}
owo(i, 0, n) {
auto it = st[i].begin();
while(it!=st[i].end()) {
int pos = i;
int diff = *it;
while(pos+diff<n) {
adj[i].senpai({pos+diff, (pos+diff-i)/diff});
if(st[pos+diff].count(diff)) break;
pos+=diff;
}
pos = i;
while(pos-diff>=0) {
adj[i].senpai({pos-diff, (i-pos+diff)/diff});
if(st[pos-diff].count(diff))break;
pos-=diff;
}
it++;
}
}
memset(dist, INF, sizeof(dist));
int start = arr[0].first;
priority_queue<ttgl, vector<ttgl>, greater<ttgl>> pq;
pq.push({0, start});
dist[start] = 0;
while(!pq.empty()) {
auto u = pq.top();
pq.pop();
if(u.first!=dist[u.second])continue;
for(auto nxt: adj[u.second]) {
if(dist[u.second]+nxt.second<dist[nxt.first]) {
dist[nxt.first] = dist[u.second]+nxt.second;
pq.push({dist[nxt.first], nxt.first});
}
}
}
if(dist[arr[1].first]==INF) {
cout<<"-1\n";
}else {
cout<<dist[arr[1].first]<<"\n";
}
return 0;
}
