#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define endl '\n'
const int MAXN = 3e4 + 10;
const int MOD = 1e9 + 7;
const ll INF = 2e18;
const int LOG = 22;
const int SQ = 300;
int n , m , B[MAXN] , P[MAXN] , dist[MAXN * SQ];
vector<pii> adj[MAXN * SQ];
map<pii , int> mark , ind;
deque<int> q;
void BFS(int v){
for(int i = 0; i < MAXN * SQ; i++){
dist[i] = MOD;
}
dist[v] = 0;
q.push_back(v);
while(q.size() > 0){
int v = q.front();
q.pop_front();
for(auto i : adj[v]){
int u = i.X , w = i.Y;
if(dist[v] + w >= dist[u]){
continue;
}
dist[u] = dist[v] + w;
if(w == 0){
q.push_front(u);
}
else{
q.push_back(u);
}
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
vector<pii> vec;
for(int i = 0; i < m; i++){
cin >> B[i] >> P[i];
if(mark[pii(P[i] , B[i])] == 0){
for(int j = B[i]; j < n; j += P[i]){
vec.push_back({P[i] , j});
mark[pii(P[i] , j)] = 1;
}
for(int j = B[i] - P[i]; j >= 0; j -= P[i]){
vec.push_back({P[i] , j});
mark[pii(P[i] , j)] = 1;
}
}
}
sort(vec.begin() , vec.end());
for(int i = 0; i < vec.size(); i++){
ind[pii(vec[i].X , vec[i].Y)] = i + n;
}
for(int i = 0; i < m; i++){
adj[B[i]].push_back({ind[pii(P[i] , B[i])] , 0});
}
for(int i = 0; i < vec.size(); i++){
int x = vec[i].X , y = vec[i].Y;
if(y + x < n){
adj[i + n].push_back({ind[pii(x , y + x)] , 1});
}
if(y - x >= 0){
adj[i + n].push_back({ind[pii(x , y - x)] , 1});
}
adj[i + n].push_back({y , 0});
}
BFS(ind[pii(P[0] , B[0])]);
if(dist[B[1]] == MOD){
cout << -1 << endl;
return 0;
}
cout << dist[B[1]] << endl;
return 0;
}
