#include <bits/stdc++.h>
using namespace std;
const int N = 30005;
const long long inf = 1e18;
set<pair<int, int>> G[N];
long long dist[N];
struct T{
int node;
long long dist;
bool operator<(const T& other)const{
return dist < other.dist;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
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){
G[b].insert({j, (j - b) / p});
}
for(int j = b;j >= 0;j -= p){
G[b].insert({j, (b - j) / p});
}
}
for(int i = 0;i < n;++i){
dist[i] = inf;
}
int s = v[0][0], t = v[1][0];
dist[s] = 0;
priority_queue<T>pq;
T temp = {s, dist[s]};
pq.push(temp);
while(!pq.empty()){
int node = pq.top().node;
long long D = pq.top().dist;
pq.pop();
if(D != dist[node])continue;
for(auto t : G[node]){
int v = t.first, w = t.second;
if(dist[v] > dist[node] + w){
dist[v] = dist[node] + w;
pq.push({v, dist[v]});
}
}
}
if(dist[t] == inf)dist[t] = -1;
cout << dist[t] << '\n';
}
