#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
const long long inf = 1e18;
long long G[N][N], dist[N];
bool used[N];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 0;i < n;++i){
for(int j = 0;j < n;++j){
G[i][j] = inf;
}
G[i][i] = 0;
dist[i] = inf;
}
vector<array<int, 2>>v(m);
for(int i = 0;i < m;++i){
int b, p;
cin >> b >> p;
v[i] = {b, p};
for(int j = b;j < n;j += p){
long long w = (j - b) / p;
G[b][j] = min(G[b][j], w);
}
for(int j = b;j >= 0;j -= p){
long long w = (b - j) / p;
G[b][j] = min(G[b][j], w);
}
}
int s = v[0][0], t = v[1][0];
dist[s] = 0;
while(true){
int mn = -1;
for(int i = 0;i < n;++i){
if(used[i])continue;
if(mn == -1 || dist[mn] > dist[i])mn = i;
}
if(mn == -1)break;
used[mn] = true;
for(int i = 0;i < n;++i){
if(G[mn][i] != inf){
dist[i] = min(dist[i], dist[mn] + G[mn][i]);
}
}
}
if(dist[t] == inf)dist[t] = -1;
cout << dist[t] << '\n';
}
