#include<bits/stdc++.h>
using namespace std;
#include<fstream>
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
typedef unsigned long long ull;
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const ll mod= 1e9 + 7;
const int mxk = 1e3, sq = 750, mxn = 3e4;
const ll inf = -1e18;
int n, m;
vt<pii>adj[mxn + 1];
int b[mxn + 1], p[mxn + 1];
set<int>s[mxn + 1];
map<int, int>alr[mxn + 1];
ll d[mxn + 1];
struct ch{
int u; ll d;
};
struct cmp{
bool operator ()(const ch &a, const ch &b){
return(a.d > b.d);
}
};
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
forr(i, 0, m){
cin >> b[i] >> p[i];
s[b[i]].insert(p[i]);
}
forr(i, 0, m){
if(alr[b[i]][p[i]])continue;
alr[b[i]][p[i]] = true;
int pos = b[i];
for(int j = pos - p[i]; j >= 0; j -= p[i]){
adj[pos].pb({j, (pos - j) / p[i]});
//cout << pos << ' ' << j << " ";
if(s[j].count(p[i]))break;
}
for(int j = pos + p[i]; j < n; j += p[i]){
adj[pos].pb({j, (j - pos) / p[i]});
if(s[j].count(p[i]))break;
}
}
for(int i = 0; i < n; i++)d[i] = 1e18;
priority_queue<ch, vt<ch>, cmp>pq; d[b[0]] = 0; pq.push({b[0], d[b[0]]});
while(pq.size()){
auto [u, dd] = pq.top(); pq.pop();
if(d[u] != dd)continue;
if(u == b[1]){
cout << d[u];
return(0);
}
for(auto [v, w]: adj[u]){
if(d[u] + w < d[v]){
d[v] = d[u] + w;
pq.push({v, d[v]});
}
}
}
cout << -1;
return(0);
}
