#include<bits/stdc++.h>
using namespace std;
const int MAXN = 30010;
const int BLOCK = 1000;
vector<int> p2bs[MAXN];
vector<int> col2p[MAXN];
vector<pair<int,int>> col2col[MAXN];
int ans[BLOCK][MAXN];
int& ans_at(int p, int x){
return ans[p + 1][x];
}
int32_t main(){
cin.tie(NULL)->sync_with_stdio(false);
int n, m; cin >> n >> m;
for(int i = 0; i < BLOCK; ++i)
for(int j = 0; j < n; ++j)
ans[i][j] = INT_MAX;
int B[2], P[2];
cin >> B[0] >> P[0];
cin >> B[1] >> P[1];
for(int i = 2; i < m; ++i){
int b, p; cin >> b >> p;
p2bs[p].push_back(b);
}
for(int p = 1; p < MAXN; ++p){
sort(p2bs[p].begin(), p2bs[p].end());
p2bs[p].erase(unique(p2bs[p].begin(), p2bs[p].end()), p2bs[p].end());
if(p + 1 < BLOCK){
for(auto b : p2bs[p]){
col2p[b].push_back(p);
}
}else{
for(auto b : p2bs[p]){
for(int i = b % p; i < n; i += p){
int dist = abs(i - b) / p;
col2col[b].push_back({i, dist});
}
}
}
}
struct Node{
int i, x;
// se i == -1, eh col
int cost;
bool operator<(const Node &n) const{
return cost > n.cost;
}
};
priority_queue<Node> pq;
deque<Node> q;
for(int i = (B[0] % P[0]); i < n; i += P[0]){
int dist = abs(i - B[0]) / P[0];
pq.push({-1, i, ans_at(-1, i) = dist});
}
// print();
while(pq.size() + q.size() > 0){
auto maybe_update = [&](int p, int x, int val, int d){
if(ans_at(p, x) > val){
Node X = {p, x, ans_at(p, x) = val};
if(d == 0) q.push_front(X);
else if(d == 1) q.push_back(X);
else pq.push(X);
}
};
Node nxt;
{
if(q.size()){
nxt = q.front();
q.pop_front();
}else{
nxt = pq.top(); pq.pop();
}
}
auto [i, x, cost] = nxt;
if(cost > ans_at(i, x)) continue;
// cout << i << " " << x << " " << cost << "\n";
if(i == -1){
for(auto p : col2p[x]){
maybe_update(p, x, cost, 0);
}
for(auto [y, ec] : col2col[x]){
maybe_update(-1, y, cost + ec, 2);
}
}else if(i + 1 < BLOCK){
// sou power i na coluna x
maybe_update(-1, x, cost, 0);
if(x + i < n){
maybe_update(i, x + i, cost + 1, 1);
}
if(x - i >= 0){
maybe_update(i, x - i, cost + 1, 1);
}
}
// print();
}
cout << ((ans_at(-1, B[1]) == INT_MAX)? -1 : ans_at(-1, B[1])) << "\n";
}
