#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
constexpr int inf = 1 << 30;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)
#define ALL(x) (x).begin(), (x).end()
template <typename T> bool chmin(T &a, const T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
vector<i64> calc_mincost(int S, vector<vector<pair<int, int>>> &g) {
const int N = (int)g.size();
vector<i64> dist(N, inf);
dist[S] = 0;
deque<int> deq;
deq.push_back(S);
while (not deq.empty()) {
const int f = deq.front();
deq.pop_front();
for (const auto &[t, c] : g[f]) {
if (chmin(dist[t], dist[f] + c)) {
if (c == 0) {
deq.push_front(t);
} else {
deq.push_back(t);
}
}
}
}
return dist;
}
int main() {
int N, M;
cin >> N >> M;
vector<pair<int, int>> A(M);
REP(i, M) {
cin >> A[i].first >> A[i].second;
chmin(A[i].second, N);
}
int S = 0, T = 0;
{
const auto as = A[0], at = A[1];
sort(ALL(A), [](auto a, auto b) {
if (a.second != b.second) {
return a.second < b.second;
}
return a.first < b.first;
});
REP(i, M) {
if (A[i] == as) S = i;
if (A[i] == at) T = i;
}
}
vector<vector<pair<int, bool>>> lst(N);
REP(i, M) {
if ((not lst[A[i].first].empty()) and lst[A[i].first].back().first == A[i].second) {
lst[A[i].first].back().second = true;
continue;
} else {
lst[A[i].first].push_back({A[i].second, true});
}
int f = A[i].first % A[i].second;
while (f < N) {
if (lst[f].empty() or lst[f].back().first != A[i].second)
lst[f].push_back({A[i].second, false});
f += A[i].second;
}
}
vector<int> size_r(N + 1);
REP(i, N) size_r[i + 1] = size_r[i] + (int)lst[i].size();
vector<unordered_map<int, int>> id_m(N);
REP(i, N) { REP(j, (int)lst[i].size()) id_m[i][lst[i][j].first] = size_r[i] + j; }
const int V = size_r[N] + N;
vector<vector<pair<int, int>>> graph(V);
REP(i, N) {
for (const auto &[w, c] : lst[i]) {
const int id = id_m[i][w];
graph[id].push_back({size_r[N] + i, 0});
if (c) graph[size_r[N] + i].push_back({id, 0});
const int l = i - w;
if (l >= 0) {
const int id2 = id_m[l][w];
graph[id2].push_back({id, 1});
graph[id].push_back({id2, 1});
}
}
}
auto dist = calc_mincost(size_r[N] + A[S].first, graph);
auto ans = dist[size_r[N] + A[T].first];
if (ans == inf) ans = -1;
cout << ans << endl;
}
