#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)
// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif
#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
advance(it, -n);
return it;
}
template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
advance(it, n);
return it;
}
#endif
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;
const double EPS = 1e-9;
const double PI = 3.141592653589793238462;
template<typename T>
inline T sq(T a) { return a * a; }
//#ifdef LOCAL_MACHINE
//#endif
const int SIZE = 175;
const int MAXN = 3e4 + 5;
const int INF = 1e9;
int dist[MAXN][SIZE];
priority_queue<pair<int, ii>, vector<pair<int, ii> >, greater<pair<int, ii> > > pq;
vi vec[MAXN];
void relax(int i, int x, int d) {
if (dist[i][x] <= d) return;
dist[i][x] = d;
pq.push(mp(d, mp(i, x)));
}
int main() {
//freopen("", "r", stdin);
//freopen("", "w", stdout);
int n, m, st = -1, en = -1;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
int b, p;
scanf("%d %d", &b, &p);
vec[b].pb(p);
if (i == 0) st = b;
if (i == 1) en = b;
}
for (int i = 0; i <= n; i++)
for (int j = 0; j < SIZE; j++)
dist[i][j] = INF;
dist[st][0] = 0;
pq.push(mp(0, mp(st, 0)));
int ans = INF;
while (!pq.empty()) {
int w = pq.top().fi;
int u = pq.top().se.fi;
int x = pq.top().se.se;
pq.pop();
if (u == en) {
ans = min(ans, w);
continue;
}
if (w >= ans) continue;
if (dist[u][x] < w) continue;
if (x == 0) {
for (auto it : vec[u]) {
if (it < SIZE) {
relax(u, it, w);
} else {
for (int v = u + it; v < n; v += it) {
relax(v, 0, w + (v - u) / it);
}
for (int v = u - it; v >= 0; v -= it) {
relax(v, 0, w + (u - v) / it);
}
}
}
} else {
relax(u, 0, w);
if (u + x < n)
relax(u + x, x, w + 1);
if (u - x >= 0)
relax(u - x, x, w + 1);
}
}
//int ans = *min_element(dist[en], dist[en] + SIZE);
if (ans == INF)
puts("-1");
else
printf("%d\n", ans);
return 0;
}
