#include <bits/stdc++.h>
#define nl '\n'
const int mxN = 30006;
std::set<std::pair<int, int>> doges[mxN];
int B[mxN], P[mxN];
int N, M;
std::vector<std::pair<int, int>> adj[mxN];
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> N >> M;
for (int i = 0; i < M; i++) {
std::cin >> B[i] >> P[i];
auto it = doges[B[i]].lower_bound({P[i], -1});
if (it == doges[B[i]].end() || it->first != P[i]) {
doges[B[i]].insert({P[i], i});
}
}
if (B[0] == B[1]) {
std::cout << 0 << nl;
return 0;
}
for (int i = 0; i < N; i++) {
for (auto [power, id] : doges[i]) {
for (int w = 1; i + w * power < N; w++) {
int to = i + w * power;
auto it = doges[to].find({power, -1});
if (it != doges[to].end() && it->first == power) {
break;
}
adj[i].emplace_back(w, to);
}
for (int w = 1; i - w * power >= 0; w++) {
int to = i - w * power;
auto it = doges[to].find({power, -1});
if (it != doges[to].end() && it->first == power) {
break;
}
adj[i].emplace_back(w, to);
}
}
}
auto dijkstra = [&](int s) -> int {
std::priority_queue<std::pair<int, int>> pq;
std::vector<int> dp(N, 1e9);
dp[s] = 0;
pq.push({0, s});
while (pq.size()) {
auto [d, u] = pq.top();
d = -d;
pq.pop();
if (dp[u] < d) continue;
for (auto [w, v] : adj[u]) {
if (dp[v] > d + w) {
dp[v] = d + w;
pq.emplace(-dp[v], v);
}
}
}
return dp[B[1]] < 1e9 ? dp[B[1]] : -1;
};
std::cout << dijkstra(B[0]) << nl;
}
