#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm>
#include <cstring>
using namespace std;
struct BruhInt {
int value = 1e9;
operator int &() { return value; }
};
constexpr int N = 3e4 + 5;
int step_size[N];
vector<int> pos2doge[N];
bool visiteddoge[N];
int dist[N];
struct SearchEntry {
int d, u;
bool operator<(const SearchEntry &other) const {
return d > other.d;
}
};
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("input.txt", "r", stdin);
int n, m;
cin >> n >> m;
int start0, start1;
for (int doge = 0; doge < m; doge++) {
int start, step;
cin >> start >> step;
if (doge == 0) start0 = start;
if (doge == 1) start1 = start;
step_size[doge] = step;
pos2doge[start].push_back(doge);
}
priority_queue<SearchEntry> pq;
pq.push({0, start0});
memset(dist, 0x3f, sizeof(dist));
dist[start0] = 0;
while (!pq.empty()) {
auto [d, pos] = pq.top();
pq.pop();
if (d > dist[pos]) continue;
if (pos == start1) {
cout << d;
return 0;
}
for (int doge : pos2doge[pos]) {
if (visiteddoge[doge]) continue;
visiteddoge[doge] = true;
int step = step_size[doge];
for (int newpos = pos, newd = d; newpos < n; newpos += step, newd++) {
if (newd >= dist[newpos]) continue;
dist[newpos] = newd;
pq.push({newd, newpos});
}
for (int newpos = pos, newd = d; newpos >= 0; newpos -= step, newd++) {
if (newd >= dist[newpos]) continue;
dist[newpos] = newd;
pq.push({newd, newpos});
}
}
}
cout << -1;
return 0;
}
