#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 30000 + 10;
const int inf = 1e9;
int b[maxn], p[maxn], dp[maxn], mark[maxn];
vector<int> vec[maxn];
int main(){
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++){
cin >> b[i] >> p[i];
vec[b[i]].push_back(p[i]);
}
for (int i = 0; i < n; i++)
dp[i] = inf;
dp[b[0]] = 0;
int cnt = 0;
for (int _ = 0; _ < n; _++){
cnt ++;
int v = -1;
for (int i = 0; i < n; i++)
if (!mark[i] and (v == -1 or dp[v] >= dp[i]))
v = i;
if (dp[v] == inf)
return cout << -1 << endl, 0;
if (v == b[1])
return cout << dp[v] << endl, 0;
if (cnt == 10000){
if (dp[b[1]] == inf)
dp[b[1]] = -1;
return cout << dp[b[1]] << endl, 0;
}
mark[v] = 1;
for (auto u : vec[v]){
for (int idx = v + u; idx < n; idx += u)
dp[idx] = min(dp[idx], dp[v] + (idx - v) / u);
for (int idx = v - u; idx >= 0; idx -= u)
dp[idx] = min(dp[idx], dp[v] + (v - idx) / u);
}
}
}
