#include <bits/stdc++.h>
#define nl '\n'
const int mxN = 30006;
std::set<int> doges[mxN];
int B[mxN], P[mxN];
int N, M;
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];
doges[B[i]].insert(P[i]);
}
if (B[0] == B[1]) {
std::cout << 0 << nl;
return 0;
}
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 (int p : doges[u]) {
for (int w = 1; u + w * p < N; w++) {
int to = u + w * p;
auto dd = dp[u] + w;
if (dd < dp[to]) {
dp[to] = dd;
pq.emplace(-dp[to], to);
}
if (doges[to].find(p) != doges[to].end()) break;
}
for (int w = 1; u - w * p >= 0; w++) {
int to = u - w * p;
auto dd = dp[u] + w;
if (dd < dp[to]) {
dp[to] = dd;
pq.emplace(-dp[to], to);
}
if (doges[to].find(p) != doges[to].end()) break;
}
}
}
return dp[B[1]] < 1e9 ? dp[B[1]] : -1;
};
std::cout << dijkstra(B[0]) << nl;
}
