// hkoi AP152 Jakarta Skyscrapers
#include <bits/stdc++.h>
#define lck cout << "ick bmi 32.9\n"
#define cam_cs cout << "ick orz\n"
#define orz(x) cout << (x) << " orz\n"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pcc pair<char, char>
#define ll long long
#define ull unsigned long long
#define ld long double
#define int long long
#define vi vector<int>
#define vll vector<long long>
#define vd vector<double>
#define vpii vector<pair<int, int>>
#define vpll vector<pair<long long, long long>>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define SET(x, a) memset((x), a, sizeof (x))
#define yes() cout << "YES\n"
#define no() cout << "NO\n"
#define impossible() cout << "Impossible\n"
#define inf 0x3f
template<typename T, typename V>
inline void print (const std::pair<T, V> &x) {std::cout << x.first << ' ' << x.second << '\n';}
template<typename T>
inline void print (const T &x) {std::cout << x << '\n';}
template<typename T>
inline void print (std::vector<T> &x) {for (auto &y : x) std::cout << y << " "; std::cout << '\n';}
inline void print () {std::cout << '\n';}
using namespace std;
ld pi = acos(-1);
ld eps = 1e-9;
ll mod = 1000000007;
inline ll powmod(ll a, ll b) {ll res = 1; a %= mod; for(; b; b >>= 1) {if (b & 1) res = res * a % mod; a = a * a % mod;} return res;}
inline ll hamming (string &a, string &b) {ll ret = 0; for (ll i = 0; i < a.length(); i++) if (a[i] != b[i]) ret++; return ret;}
inline bool isprime (ll x) {if (x == 2) return true; for (ll i = 2; i * i <= x; i++) {if (x % i == 0) return false;}; return true;}
inline double Dist (double x1, double y1, double x2, double y2) {return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));}
inline ll manhattan (ll x1, ll y1, ll x2, ll y2) {return abs(x1 - x2) + abs(y1 - y2);}
clock_t T, NT;
inline double get_time() {NT = clock() - T; return (double)(NT) / CLOCKS_PER_SEC;}
struct dsu {
int n;
vector<int> parent;
vector<int> sz;
dsu (int _n) : n(_n) {
parent.resize(n + 5);
iota(all(parent), 0);
sz.assign(n, 1);
}
inline void init (int _n) {n = _n; parent.resize(n); iota(all(parent), 0); sz.assign(n, 1);}
inline void init () {iota(all(parent), 0); sz.assign(n, 1);}
inline int Find (int x) {return parent[x] == x ? x : parent[x] = Find(parent[x]);}
inline bool Union (int x, int y) {
x = Find(x), y = Find(y);
if (x != y) {
parent[x] = y;
sz[y] += sz[x], sz[x] = 0;
return true;
}
else return false;
}
};
struct segment_tree {
ll n;
vll a; // 1-based
vll seg; // 1-based
segment_tree (int _n) : n(_n) {
a.resize(n + 5);
seg.resize(4 * n + 5);
}
inline void build (int l, int r, int id = 1) {
if (l == r) {seg[id] = a[l]; return;}
ll mid = (l + r) >> 1;
build(l, mid, id << 1);
build(mid + 1, r, id << 1 | 1);
seg[id] = max(seg[id << 1], seg[id << 1 | 1]); // SUBJECT TO CHANGE ACCORDING TO TASK
}
inline ll query (int lq, int rq, int l, int r, int id = 1) {
if (r < lq || rq < l) return -1;
else if (lq <= l && r <= rq) return seg[id];
ll mid = (l + r) >> 1;
ll v1 = query(lq, rq, l, mid, id << 1);
ll v2 = query(lq, rq, mid + 1, r, id << 1 | 1);
if (v1 == -1) return v2;
else if (v2 == -1) return v1;
else return max(v1, v2); // SUBJECT TO CHANGE ACCORDING TO TASK
}
};
struct TopoSort {
int n;
vi in, ans;
vector<vi> adj;
inline void init (int _n) {n = _n; in.assign(n, 0); adj.assign(n, vector<int> (0));}
inline void conn (int x, int y) {adj[x].push_back(y), ++in[y];}
inline bool sort () {
queue<int> q;
for (int i = 0; i < n; i++) if (!in[i]) q.push(i);
while (!q.empty()) {
int curr = q.front();
q.pop();
ans.push_back(curr);
for (auto &x : adj[curr]) if (!(--in[x])) q.push(x);
}
return ans.size() == n;
}
};
struct Fenwick {
ll n;
vll a;
Fenwick (ll _n): n(_n), a(_n) {}
void add (ll x, ll val) {
for (int i = x + 1; i <= n; i += i & -i) a[i - 1] += val;
}
ll sum (ll x) {
ll ans = 0;
for (int i = x; i >= 1; i -= i & -i) ans += a[i - 1];
return ans;
}
ll range_sum (ll l, ll r) {return sum(r) - sum(l);}
};
/*
>>>>>>>>>>>>>>>>>>>>>>>>>>END OF TEMPLATE HEADER<<<<<<<<<<<<<<<<<<<<<<<<
*/
pii a[30005];
vi adj[30005];
bitset<30005> visited[30005];
void solve (int &tc) {
int n, m; cin >> n >> m;
int s, e;
SET(visited, false);
for (int i = 0; i < m; i++) {
cin >> a[i].fi >> a[i].se;
if (!i) s = a[i].fi;
if (i == 1) e = a[i].fi;
if (0 <= a[i].fi + a[i].se && a[i].fi + a[i].se < n) adj[a[i].fi].push_back(a[i].se);
if (0 <= a[i].fi - a[i].se && a[i].fi - a[i].se < n) adj[a[i].fi].push_back(-a[i].se);
}
queue<pair<int, pii>> q;
q.push({s, {0, 0}});
pair<int, pii> curr;
while (!q.empty()) {
curr = q.front();
q.pop();
if (curr.fi == e) {
print((curr.se.fi));
return;
}
if (0 <= curr.fi + curr.se.se && curr.fi + curr.se.se < n && !visited[curr.fi][curr.fi + curr.se.se]) {
q.push({curr.fi + curr.se.se, {curr.se.fi + 1, curr.se.se}});
visited[curr.fi].set(curr.fi + curr.se.se);
}
for (auto &x : adj[curr.fi]) {
if (x && !visited[curr.fi][curr.fi + x]) q.push({curr.fi + x, {curr.se.fi + 1, x}}), visited[curr.fi].set(curr.fi + x);
}
}
print((-1));
}
signed main () {
cin.tie()->sync_with_stdio(false);
T = clock();
srand(time(NULL));
int t = 1;
// cin >> t;
for (int i = 1; i <= t; i++) {
solve(i);
// if (i != t) cout << '\n';
}
// while (true) {solve(t); t++;}
return 0;
}
// g++ -std=c++17 file_name.cpp -o file_name
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
