#include <bits/stdc++.h>
using namespace std;
#define Task "SKY"
#define ll long long
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define F first
#define S second
typedef pair<int, int> ii;
const int N = 5e4 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;
template<class X, class Y>
bool minimize(X &x, Y y) {
if (x > y) {
x = y;
return true;
} else return false;
}
template<class X, class Y>
bool maximize(X &x, Y y) {
if (x < y) {
x = y;
return true;
} else return false;
}
int n, m;
vector<set<int>> powers;
int dist[N];
vector<pair<int, int>> adj[N];
int s, e;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(Task".INP", "r")) {
freopen(Task".INP", "r", stdin);
freopen(Task".OUT", "w", stdout);
}
cin >> n >> m;
powers.resize(n + 1);
FOR(i, 0, m - 1) {
int building, power;
cin >> building >> power;
powers[building].insert(power);
if (i == 0) s = building;
if (i == 1) e = building;
}
FOR(i, 0, n - 1) {
for (int power : powers[i]) {
FOR(j, 1, (n - i) / power) {
int nxt = i + j * power;
adj[i].push_back({nxt, j});
if (powers[nxt].count(power)) break;
}
FOR(j, 1, i / power) {
int nxt = i - j * power;
if (nxt < 0) break;
adj[i].push_back({nxt, j});
if (powers[nxt].count(power)) break;
}
}
}
priority_queue<ii, vector<ii>, greater<ii>> pq;
memset(dist, 0x3f, sizeof(dist));
pq.push({0, s});
dist[s] = 0;
while(!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (u == e) {
cout << d;
return 0;
}
if (d > dist[u]) continue;
for (auto [v, w] : adj[u]) if (minimize(dist[v], dist[u] + w)) {
pq.push({dist[v], v});
}
}
cout << -1;
return 0;
}
