#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
using ld = long double;
using db = double;
///--------------------------------
#define F first
#define S second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define mem(f, x) memset(f, x, sizeof(f))
#define uniqueV(x) sort(all(x)), (x).resize(unique(all(x)) - x.begin())
template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }
///--------------------------------
#define PROBLEM "test"
const int MOD = 1e9 + 7; // 998244353;
const ll INF = 1e18;
const ld eps = 1e-9;
const ld PI = acos(-1);
const int dx[4]{0, 1, 0, -1}, dy[4]{1, 0, -1, 0}; // R D L U
const int ddx[4]{-1, 1, 1, -1}, ddy[4]{1, 1, -1, -1}; // UR DR DL UL
///--------------------------------
void precalc();
void solve();
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(PROBLEM".inp", "r")) {
freopen(PROBLEM".inp", "r", stdin);
freopen(PROBLEM".out", "w", stdout);
}
constexpr bool MULTI_TEST = 0;
int t = 1;
if (MULTI_TEST) cin >> t;
while (t--)
solve();
// cerr << setprecision(3) << fixed;
// cerr << "[" << 1.0 * clock() / CLOCKS_PER_SEC << "s] ";
}
///--------------------[PROBLEM SOLUTION]--------------------///
const int BLOCKSZ = 200;
const int maxn = 30030;
ll dist[maxn][BLOCKSZ + 1];
bool vis[maxn][BLOCKSZ + 1];
bool exist[maxn][BLOCKSZ + 1];
ll P[maxn], B[maxn];
void solve() {
ll n, m;
cin >> n >> m;
mem(exist, false);
for (int i = 0; i < m; i++) {
cin >> B[i] >> P[i];
if (P[i] < BLOCKSZ)
exist[B[i]][P[i]] = true;
}
mem(dist, 0x3f);
mem(vis, false);
priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
if (P[0] < BLOCKSZ) {
dist[B[0]][P[0]] = 0;
pq.push({0, B[0], P[0]});
}
dist[B[0]][BLOCKSZ] = 0;
pq.push({0, B[0], BLOCKSZ});
while (pq.size()) {
int x = pq.top()[1], y = pq.top()[2]; pq.pop();
if (vis[x][y]) continue;
vis[x][y] = true;
if (y == BLOCKSZ) {
for (int i = 1; i < BLOCKSZ; i++) {
if (!vis[x][i] && exist[x][i]
&& minimize(dist[x][i], dist[x][y]))
pq.push({dist[x][i], x, i});
}
continue;
}
if (y < BLOCKSZ) {
//dummy vertex
if (x - y >= 0 && !vis[x - y][BLOCKSZ]
&& minimize(dist[x - y][BLOCKSZ], dist[x][y] + 1))
pq.push({dist[x - y][BLOCKSZ], x - y, BLOCKSZ});
if (x + y < n && !vis[x + y][BLOCKSZ]
&& minimize(dist[x + y][BLOCKSZ], dist[x][y] + 1))
pq.push({dist[x + y][BLOCKSZ], x + y, BLOCKSZ});
//direct path
if (x - y >= 0 && !vis[x - y][y]
&& minimize(dist[x - y][y], dist[x][y] + 1))
pq.push({dist[x - y][y], x - y, y});
if (x + y < n && !vis[x + y][y]
&& minimize(dist[x + y][y], dist[x][y] + 1))
pq.push({dist[x + y][y], x + y, y});
}
else {
for (int nx = x % y; nx < n; nx += y) {
if (!vis[nx][BLOCKSZ]
&& minimize(dist[nx][BLOCKSZ], dist[x][y] + abs(nx - x) / y))
pq.push({dist[nx][BLOCKSZ], nx, BLOCKSZ});
}
}
}
cout << (!vis[B[1]][BLOCKSZ] ? -1 : dist[B[1]][BLOCKSZ]) << '\n';
}
