#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
priority_queue<pii,vector<pii>,greater<pii>> pq;
vector<ll> doges[30002];
bool vis[30002];
ll jmp[30002];
ll odl[30002];
ll n,m,oo=1e14;
void Dijkstra(ll pos, ll kon){
fill(odl,odl+n,oo);
odl[pos]=0;
pq.push({0,pos});
ll iter;
while(pq.size()){
auto [d,v]=pq.top();
pq.pop();
if (d>odl[v])continue;
if (v==kon)break;
for (auto u : doges[v]) if (!vis[u]){
vis[u]=true;
iter=1;
for (ll i = v+jmp[u]; i<n; i+=jmp[u]){
if (odl[i]>d+iter){
odl[i]=d+iter;
pq.push({d+iter,i});
}
iter++;
}
iter=1;
for (ll i = v-jmp[u]; i>=0; i-=jmp[u]){
if (odl[i]>d+iter){
odl[i]=d+iter;
pq.push({d+iter,i});
}
iter++;
}
}
}
if (odl[kon]==oo)cout << "-1\n";
else cout << odl[kon] << '\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll b,p,st,nd;
cin >> n >> m;
cin >> st >> jmp[1];
doges[st].push_back(1);
cin >> nd >> p;
for (ll i = 2; i<m; i++){
cin >> b >> jmp[i];
doges[b].push_back(i);
}
Dijkstra(st,nd);
}
