// Only GOD
// believe in yourself
// Nemidam Del Be In Darde Donya!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define bit(x, y) ((x >> y)&1)
#define sz(x) (int)x.size()
#define kill(x) return cout << x << '\n', void()
#define KILL(x) return cout << x << '\n', 0
#define int ll
const int N = 1e5+100;
const int INF = 1e9+10;
set <int> s[N];
vector<pii> G[N];
int dis[N];
int32_t main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n, m;
cin >> n >> m;
int start = -1, end = -1;
for(int i = 0; i < m; i++){
int b, p;
cin >> b >> p;
s[b].insert(p);
if(i==0)
start = b;
if(i==1)
end = b;
}
memset(dis, 63, sizeof dis);
for(int i = 0; i < n; i++){
for(int u : s[i]){
for(int j = i+u;j < n; j+= u){
G[i].pb({j, (j-i)/u});
if(s[j].find(u) != s[j].end()){
break;
}
}
for(int j = i - u; j >= 0; j-=u){
G[i].pb({j, (i-j)/u});
if(s[j].find(u) != s[j].end()){
break;
}
}
}
}
dis[start] = 0;
priority_queue<pii> q;
q.push({-dis[start], start});
while(!q.empty()){
int a = q.top().S;
q.pop();
for(auto B : G[a]){
int v = B.F, w = B.S;
if(dis[a] + w < dis[v]){
dis[v] = dis[a]+w;
q.push({-dis[v], v});
}
}
}
cout << (dis[end] > INF ? -1 : dis[end]);
}
