#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, git[N], b[N], p[N];
vector <pii> v[N];
priority_queue <pii> pq;
vector <int> dis(N,1e9);
void f(){
pq.push({0,b[1]});
dis[b[1]] = 0;
while(!pq.empty()){
int a = pq.top().ss;
pq.pop();
for(pii 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];
git[b[i]] = p[i];
}
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(git[nd] == p[i]) break;
}
nd = b[i], cnt = 0;
while(1) {
nd += p[i];
if(nd > n-1) break;
cnt++;
v[b[i]].pb({nd,cnt});
if(git[nd] == p[i]) break;
}
}
// for(int i = 0; i < n; i++){
// cout << i << '\n';
// for(auto j: v[i]) cout << j.ff << ' ' << j.ss << '\n';
// }
f();
cout << (dis[b[2]] == 1e9 ? -1 : dis[b[2]]);
}
