#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'
inline void solve(){
int n, m, st, dt;
cin>>n>>m;
vector<pair<int,int>> g[n];
set<int> unused[n];
for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(i != j) unused[i].insert(j);
for(int i=0; i<m; i++){
int b, p;
cin>>b>>p;
if(i == 0) st = b;
if(i == 1) dt = b;
for(int x : unused[b]){
if(abs(x - b) % p == 0) g[b].push_back({x, abs(x - b)/p});
}
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
vector<int> vis(n, 0);
vector<int> dist(n, 1e18);
pq.push({0, st});
dist[st] = 0;
while(!pq.empty()){
auto [d, v] = pq.top();
pq.pop();
if(vis[v]) continue;
vis[v] = 1;
for(auto [ch, w] : g[v]){
if(d + w < dist[ch]){
dist[ch] = d + w;
pq.push({dist[ch], ch});
}
}
}
cout<<(dist[dt] == 1e18 ? -1 : dist[dt])<<nl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);cout.tie(NULL);
int t = 1;
//cin>>t;
while(t--) solve();
return 0;
}
