#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 1e9;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m; cin>>n>>m;
vector<int> x(m + 1), y(m + 1);
for (int i = 1; i <= m; i++){
cin>>x[i]>>y[i];
x[i]++;
}
vector<vector<int>> ww(n + 1, vector<int>(n + 1, inf));
for (int i = 1; i <= m; i++){
int f = x[i] + y[i], cc = 1;
while (f <= n){
ww[x[i]][f] = min(ww[x[i]][f], cc);
f += y[i]; cc++;
}
f = x[i] - y[i]; cc = 1;
while (f > 0){
ww[x[i]][f] = min(ww[x[i]][f], cc);
f -= y[i]; cc++;
}
}
vector<pii> g[n + 1];
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (ww[i][j] != inf){
g[i].pb({j, ww[i][j]});
}
}
}
priority_queue<pii, vector<pii>, greater<pii>> pq; pq.push({0, x[1]});
vector<int> out(n + 1, inf); out[x[1]] = 0;
while (!pq.empty()){
auto [d, v] = pq.top(); pq.pop();
for (auto [u, w]: g[v]){
int s = d + w;
if (s < out[u]){
out[u] = s;
pq.push({out[u], u});
}
}
}
cout<<((out[x[2]] == inf) ? -1 : out[x[2]])<<"\n";
}
