#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;
priority_queue<pair<int, int>> q1;
const int MAXN = 30010;
set<int> v1[MAXN];
vector<pair<int, int>> g[MAXN];
bool visited[MAXN];
int dp[MAXN];
int target;
int first, jump;
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int b, p;
cin >> b >> p;
if (i == 0) {
first = b;
jump = p;
}
if (i == 1) {
target = b;
}
v1[b].insert(p);
}
for (int i = 0; i <= n; i++) {
for (int x : v1[i]) {
int b = i;
int p = x;
int count = 1;
for (int j = b + p; j <= n; j += p) {
// cout<<i<<" "<<j<<endl;
if (v1[j].find(p) != v1[j].end()) {
g[b].push_back(make_pair(j, count));
break;
}
g[b].push_back(make_pair(j, count));
count++;
}
count = 1;
for (int j = b - p; j >= 0; j -= p) {
if (v1[j].find(p) != v1[j].end()) {
g[b].push_back(make_pair(j, count));
break;
}
g[b].push_back(make_pair(j, count));
count++;
}
}
}
q1.push(make_pair(0, first));
for (int i = 0; i <= n; i++) {
dp[i] = 1e9;
}
dp[first] = 0;
while (!q1.empty()) {
auto hold = q1.top();
int skyscraper = hold.second;
int dist = -1 * hold.first;
q1.pop();
if (skyscraper == target) {
cout << dist << endl;
return 0;
}
if (visited[skyscraper]) {
continue;
}
visited[skyscraper] = true;
for (auto x : g[skyscraper]) {
int w = x.second;
int to = x.first;
if (dp[to] > dp[skyscraper] + w) {
dp[to] = dp[skyscraper] + w;
q1.push(make_pair(-1 * dp[to], to));
}
}
}
cout << -1 << endl;
}
