#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 30005
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007LL
priority_queue<pair<int, int> > pq;
vector<int> dog[N];
bool vis[N];
int dist[N];
int n;
void go(int v){
vis[v] = 1;
for(int& x : dog[v]){
for(int i = v + x, a = 1; i < n; i += x, ++a){
if(dist[i] > dist[v] + a){
dist[i] = dist[v] + a;
pq.push({-dist[i], i});
}
}
for(int i = v - x, a = 1; i >= 0; i -= x, ++a){
if(dist[i] > dist[v] + a){
dist[i] = dist[v] + a;
pq.push({-dist[i], i});
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int m;
cin>>n>>m;
int b, p;
int s, e;
cin>>s>>p;
dog[s].push_back(p);
cin>>e>>p;
dog[e].push_back(p);
m -= 2;
memset(dist, 0x3f, sizeof dist);
while(m--){
cin>>b>>p;
dog[b].push_back(p);
}
pq.push({0, s});
dist[s] = 0;
while(!pq.empty()){
int a = pq.top().ss;
pq.pop();
if(a == e){
cout<<dist[e];
return 0;
}
if(!vis[a])
go(a);
}
cout<<-1;
}
