#include<bits/stdc++.h>
using namespace std;
#define dlwlrma ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define f first
#define s second
const int mxN = 30002;
int n,m,src,dest,vis[mxN];
set<int>doge[mxN];
vector<pii>chu[mxN];
priority_queue<pii>pq;
int main(){
dlwlrma
cin >> n >> m;
for(int i = 0; i < m; i++){
int b,p;
cin >> b >> p;
if(i==0)
src=b;
if(i==1)
dest=b;
doge[b].insert(p);
}
for(int i = 0; i < n; i++){
for(int next : doge[i]){
for(int j = i + next, cnt = 1; j < n; j+=next,cnt++){
chu[i].push_back({j,cnt});
if(doge[j].find(next)!=doge[j].end())
break;
}
for(int j = i - next, cnt = 1; j >= 0; j-=next, cnt++){
chu[i].push_back({j,cnt});
if(doge[j].find(next)!=doge[j].end())
break;
}
}
}
memset(vis,0x3f,sizeof(vis));
pq.push({0,src});
vis[src]=0;
while(!pq.empty()){
pii cur = pq.top(); pq.pop();
int dist = cur.f, node = cur.s;
if(node == dest){
cout << dist << "\n";
return 0;
}
for(pii next : chu[node]){
if(next.s - dist < vis[next.f]){
vis[next.f]= next.s - dist;
pq.push({dist+next.s,next.f});
}
}
}
cout << -1 << "\n";
}
