#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <iomanip>
#include <stack>
#include <fstream>
using namespace std;
int menor(vector<vector<int> >&mov,int z,int u){
int n=mov.size();
vector<int>d(n,1e9);
priority_queue<pair<int,int > >pq;
pq.push(make_pair(0,z));
d[z]=0;
while(!pq.empty()){
int t=pq.top().first;
t*=-1;
int nt=pq.top().second;
if(t>=d[u])break;
pq.pop();
if(t>d[nt])continue;
if(nt!=u){
for(int c:mov[nt]){
int x=nt+c,o=1+d[nt];
while(x<=n-1 && o<d[u]){
if(o<d[x]){
d[x]=o;
pq.push(make_pair(-d[x],x));
}
if(x==u)x=1e9;
x+=c;
o++;
}
int a=nt-c,l=1+d[nt];
if(pq.top().first>=d[u])break;
while(a>=0 && l<d[u]){
if(l<d[a]){
d[a]=l;
pq.push(make_pair(-d[a],a));
}
if(a==u)x=-1;
l++;
a-=c;
}
if(pq.top().first>=d[u])break;
}
}
}
if(d[u]==1e9){
return -1;
}
else{
return d[u];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n,m,a,k;
cin>>n>>m;
vector<vector<int> >mov(n);
vector<int>g(m);
cin>>g[0]>>k;
mov[g[0]].push_back(k);
cin>>g[1]>>a;
mov[g[1]].push_back(a);
bool b=false;
if((g[0]-g[1])%k==0)b=true;
for(int i=2;i<m;i++){
cin>>g[i]>>a;
mov[g[i]].push_back(a);
if((g[i]-g[1])%a==0)b=true;
}
if(!b)cout<<-1;
else
cout<<menor(mov,g[0],g[1]);
return 0;
}
