#include "bits/stdc++.h"
#define ll long long int
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define sz size()
const int N = 2e5 + 1;
using namespace std;
int n, m, b[N], p[N];
vector <vector<pii>> v;
priority_queue <pii> pq;
vector <int> dis(N,1e9);
map <pii,int> mp;
void f(){
pq.push({0,b[1]});
dis[b[1]] = 0;
while(!pq.empty()){
int a = pq.top().ss;
pq.pop();
for(auto i: v[a]){
if(dis[a] + i.ss < dis[i.ff]){
dis[i.ff] = dis[a] + i.ss;
pq.push({-dis[i.ff],i.ff});
}
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
//freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> b[i] >> p[i];
mp[{b[i],p[i]}] = 1;
}
v.resize(n+1);
for(int i = 1; i <= m; i++){
int nd = b[i], cnt = 0;
while(1){
nd -= p[i];
if(nd < 0) break;
cnt++;
v[b[i]].pb({nd,cnt});
if(mp.find({nd,p[i]}) != mp.end()) break;
}
nd = b[i], cnt = 0;
while(1){
nd += p[i];
if(nd > n-1) break;
cnt++;
v[b[i]].pb({nd,cnt});
if(mp.find({nd,p[i]}) != mp.end()) break;
}
}
f();
cout << (dis[b[2]] == 1e9 ? -1 : dis[b[2]]);
}
