/**
* author: NimaAryan
* created: 2023-11-17 08:21:07
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#endif
using i64 = long long;
template <typename T = i64>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename T = i64>
using max_heap = priority_queue<T, vector<T>, less<T>>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<int> B(M), P(M);
for (int i = 0; i < M; ++i) {
cin >> B[i] >> P[i];
}
vector<vector<int>> at(N);
for (int i = 0; i < M; ++i) {
at[B[i]].push_back(P[i]);
}
constexpr int inf = numeric_limits<int>::max();
vector<int> dist(N, inf);
vector<bool> vis(N);
min_heap<pair<int, int>> h;
auto add = [&](int v, int c) {
if (c < dist[v]) {
h.emplace(dist[v] = c, v);
}
};
add(B[0], 0);
while (!h.empty()) {
auto [cd, v] = h.top();
h.pop();
if (cd > dist[v]) {
continue;
}
vis[v] = true;
for (int p : at[v]) {
for (int t = 1; v + t * p < N; ++t) {
int u = v + t * p;
add(u, cd + t);
}
for (int t = 1; v - t * p >= 0; ++t) {
int u = v - t * p;
add(u, cd + t);
}
}
}
cout << (vis[B[1]] ? dist[B[1]] : -1) << "\n";
return 0;
}
