#include <bits/stdc++.h>
#define task ""
#define fi first
#define se second
#define pii pair<int, int>
using namespace std;
using ll = long long;
const ll mod = 998244353;
const int inf = 1e9 + 1;
const int arr = 200001;
const int BLOCK = 100;
struct node{
int dis, i, p;
};
bool operator > (node a, node b) {
return a.dis > b.dis;
}
int n, m, p[30004], b[30004];
vector<int> adj[30004];
int d[30004][104];
int res = 1e9;
void solve(){
memset(d, 0x3f, sizeof d);
priority_queue<node, vector<node>, greater<node>> pq;
pq.push({0, b[0], 0});
d[b[0]][0] = 0;
while(!pq.empty()){
node k = pq.top(); pq.pop();
int dist = k.dis, pk = k.p, i = k.i;
if(i == b[1])res = min(res, dist);
if(dist != d[i][pk])continue;
if(pk == 0){
for(auto v : adj[i]){
if(p[v] <= BLOCK){
if(d[i][p[v]] > dist){
d[i][p[v]] = dist;
pq.push({dist, i, p[v]});
}
}
else{
int pp = p[v];
int cnt = 0;
for (int x = i ; x < n ; x += pp) {
if (d[x][0] > dist + cnt) {
d[x][0] = dist + cnt;
pq.push({dist + cnt , x , 0});
}
cnt++;
}
cnt = 0;
for (int x = i ; x >= 0 ; x -= pp) {
if (d[x][0] > dist + cnt) {
d[x][0] = dist + cnt;
pq.push({dist + cnt , x , 0});
}
cnt++;
}
}
}
}
else{
if (i + pk < n && d[i + pk][pk] > dist + 1) {
d[i + pk][pk] = dist + 1;
pq.push({dist + 1 , i + pk , pk});
}
if (i - pk >= 0 && d[i - pk][pk] > dist + 1) {
d[i - pk][pk] = dist + 1;
pq.push({dist + 1 , i - pk , pk});
}
if (d[i][0] > dist) {
d[i][0] = dist;
pq.push({dist , i , 0});
}
}
}
if(res == 1e9)cout << -1 << '\n';
else cout << res << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
// freopen(task".inp" , "r" , stdin);
// freopen(task".out" , "w" , stdout);
cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> b[i] >> p[i];
adj[b[i]].push_back(i);
}
solve();
}
