#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ww first
#define vv second
typedef long long ll;
typedef pair<ll, ll> llll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
int N, M, b[30'050], p[30'050];
ll sssp[30'050];
vvi dogesAt;
bitset<30'050> visited;
void bfs() {
memset(sssp, -1, sizeof sssp);
queue<iii> q;
for (int doge : dogesAt[b[0]]) {
sssp[doge] = 0;
visited[doge] = 1;
if (doge == 1) return;
q.push({b[0], {p[doge], 0}});
q.push({b[0], {-p[doge], 0}});
}
while (!q.empty()) {
iii u = q.front(); q.pop();
//cerr << "// {" << u.fi << ", {" << u.se.fi << ", " << u.se.se << "}}\n";
int newPos = u.fi + u.se.fi;
if (newPos >= 0 && newPos < N) {
q.push({newPos, {u.se.fi, u.se.se + 1}});
for (int doge : dogesAt[newPos]) if (!visited[doge]) {
sssp[doge] = u.se.se + 1;
visited[doge] = 1;
if (doge == 1) return;
q.push({newPos, {p[doge], u.se.se + 1}});
q.push({newPos, {-p[doge], u.se.se + 1}});
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
dogesAt.assign(N + 20, vi());
for (int i = 0; i < M; i++) {
cin >> b[i] >> p[i];
dogesAt[b[i]].push_back(i);
}
bfs();
//cerr << "// sssp :";
//for (int i = 0; i < M; i++) cerr << ' ' << sssp[i];
//cerr << '\n';
cout << sssp[1] << '\n';
}
