#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Node{
int i, x;
// se i == -1, eh col
int cost;
bool operator<(const Node &n) const{
return cost > n.cost;
}
};
namespace smallpq{
const int MAXV = 1e6;
queue<Node> q[MAXV];
int tot_in[MAXV];
int tot_out[MAXV];
class QComp{ public:
bool operator()(int a, int b){
return q[a].front() < q[b].front();
}
};
int _size = 0;
priority_queue<int, vector<int>, QComp> pq;
int size() { return _size; }
void push(Node x, int w) {
q[w].push(move(x));
if(++tot_in[w] - tot_out[w] == 1) pq.push(w);
_size++;
}
Node top() { return q[pq.top()].front(); }
void pop() {
auto w = pq.top(); pq.pop();
q[w].pop();
if(q[w].size()) pq.push(w);
tot_out[w]++;
_size--;
}
};
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 30010;
vector<int> col2i[MAXN];
vector<int> ans[MAXN];
int ps[MAXN];
int x2j(int id, int x){
int p = ps[id];
return x / p;
}
int& ans_at(int i, int x){
if(i == -1)
return ans[i + 1][x];
else
return ans[i + 1][x2j(i, x)];
}
map<pair<int,int>, vector<int>> pb2bs;
int32_t main(){
cin.tie(NULL)->sync_with_stdio(false);
int n, m; cin >> n >> m;
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;
pb2bs[make_pair(p, b % p)].push_back(b);
}
ans[0] = vector<int>(n, INT_MAX);
int id = 0;
for(auto [pb, bs] : pb2bs){
auto [p, b] = pb;
ps[id] = p;
for(int j = b; j < n; j += p){
ans[id+1].push_back(INT_MAX);
}
for(auto bb : bs){
col2i[bb].push_back(id);
}
id++;
}
for(int i = (B[0] % P[0]); i < n; i += P[0]){
int dist = abs(i - B[0]) / P[0];
smallpq::push({-1, i, ans_at(-1, i) = dist}, dist);
}
// print();
while(smallpq::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};
smallpq::push(X, d);
}
};
auto [i, x, cost] = smallpq::top();
smallpq::pop();
if(cost > ans_at(i, x)) continue;
// cout << i << " " << x << " " << cost << "\n";
if(i == -1){
for(auto i : col2i[x]){
maybe_update(i, x, cost, 0);
}
}else{
// sou power i na coluna x
maybe_update(-1, x, cost, 0);
if(x + ps[i] < n){
maybe_update(i, x + ps[i], cost + 1, 1);
}
if(x - ps[i] >= 0){
maybe_update(i, x - ps[i], cost + 1, 1);
}
}
// print();
}
cout << ((ans_at(-1, B[1]) == INT_MAX)? -1 : ans_at(-1, B[1])) << "\n";
}
