#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define sz(v) (int)(v).size()
#define all(v) begin(v),end(v)
#define each(e,v) for(auto &e:(v))
#define pb push_back
#define f first
#define s second
typedef long long ll;
const ll INF = 1e18;
template<class T> bool ckmin(T&a, const T&b) {
return b < a ? a = b, 1 : 0;
}
const int MX = 3e4+5;
int N,M, st,p,en;
set<int> jmp[MX];
vector<pair<ll,int>> g[MX];
ll d[MX];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
void solve() {
cin>>N>>M;
cin>>st>>p;
jmp[st].insert(p);
cin>>en>>p;
FOR(i,2,M) {
int b;
cin>>b>>p;
jmp[b].insert(p);
}
F0R(i,N) {
each(p,jmp[i]) {
for(int j = 1; ; j++) {
int pos = i+j*p;
if(pos<0 || pos>=N) break;
g[i].pb({pos,j});
if(jmp[pos].count(p)) break;
}
}
}
F0R(i,N) {
each(p,jmp[i]) {
for(int j = 1;; j++) {
int pos = i-j*p;
if(pos<0 || pos>=N) break;
g[i].pb({pos,j});
if(jmp[pos].count(p)) break;
}
}
}
memset(d,0x3f,sizeof d);
pq.push({d[st] = 0, st});
while(sz(pq)) {
int u = pq.top().s; ll du = pq.top().f;
pq.pop();
if(du > d[u]) continue;
F0R(i,sz(g[u])) {
int v = g[u][i].f; ll dv = du + g[u][i].s;
if(ckmin(d[v],dv)) {
pq.push({d[v],v});
}
}
}
if(d[en] >= INF) {
cout << "-1\n";
}
else cout << d[en] << "\n";
}
int main() {
int t=1;
//cin>>t;
while(t-->0) solve();
}
