#include <bits/stdc++.h>
using namespace std;
vector<int> smallpowers[30000]; //on given skyscraper
vector<pair<int,int>> adjlist[30000]; //weight, node
int n;
int sqv;
int INF = 1e9;
int distances[30000][175];
int dijkstra(int startloc, int endloc){
int start = startloc;
for (int i = 0; i<n; i++){
for (int j = 0; j<int(sqv)+1; j++){
distances[i][j]=INF;
}
}
distances[start][0]=0;
//priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,less<pair<int,pair<int,int>>>> pq;
set<pair<int,pair<int,int>>> pq;
pq.insert({0,{start,0}});
while (pq.size()>0){
//auto f = pq.top();
//pq.pop();
auto f = *pq.begin();
pq.erase(pq.begin());
if (distances[f.second.first][f.second.second]<f.first){
continue;
}
int curdist = f.first;
int curnode = f.second.first;
int curind = f.second.second;
if (curind==0){
// we can go to a doge with cost 0
for (int i : smallpowers[curnode]){
if (distances[curnode][i]>curdist){
distances[curnode][i]=curdist;
pq.insert({distances[curnode][i],{curnode,i}});
}
}
// or we can jump skyscrapers
for (auto p : adjlist[curnode]){
if (distances[p.second][0]>curdist+p.first){
distances[p.second][0]=curdist+p.first;
pq.insert({distances[p.second][0],{p.second,0}});
}
}
} else {
//we can go to central node with cost 0
if (distances[curnode][0]>curdist){
distances[curnode][0]=curdist;
pq.insert({distances[curnode][0],{curnode,0}});
}
//or we can go to an adjacent node
if (curnode-curind>=0&&distances[curnode-curind][curind]>curdist+1){
distances[curnode-curind][curind]=curdist+1;
pq.insert({distances[curnode-curind][curind],{curnode-curind,curind}});
}
if (curnode+curind<n&&distances[curnode+curind][curind]>curdist+1){
distances[curnode+curind][curind]=curdist+1;
pq.insert({distances[curnode+curind][curind],{curnode+curind,curind}});
}
}
}
return distances[endloc][0];
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
int m;
cin>>n>>m;
sqv = sqrt(n);
//smallpowers.resize(n);
//adjlist.resize(n);
int startloc = 0;
int endloc = 0;
for (int i = 0; i<m; i++){
int b,p;
cin>>b>>p;
if (i==0){
startloc=b;
}
if (i==1){
endloc=b;
}
//skyscraper b, moves p
if (p<sqv){
smallpowers[b].push_back(p);
} else {
int cnt = 0;
for (int x = b+p; x<n; x+=p){
cnt++;
adjlist[b].push_back({cnt,x});
}
cnt = 0;
for (int x = b-p; x>=0; x-=p){
cnt++;
adjlist[b].push_back({cnt,x});
}
}
}
int d = dijkstra(startloc,endloc);
if (d==INF){
cout<<-1<<'\n';
} else {
cout<<d<<'\n';
}
}
