#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'
int g[2000][2000];
inline void solve(){
int n, m, st, dt;
cin>>n>>m;
for(int i=0; i<n; i++) for(int j=0; j<n; j++) g[i][j] = 2e18;
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 j=b-p, c = 1; j>=0; j -= p, c++) g[b][j] = min(g[b][j], c);
for(int j=b+p, c = 1; j<n; j += p, c++) g[b][j] = min(g[b][j], c);
}
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(int ch=0; ch<n; ch++){
int w = g[v][ch];
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;
}
