#include <queue>
#include <cstdio>
#include <tuple>
#include <cstring>
#define pii pair<int, int>
#define piii tuple<int, int, int>
#define mt make_tuple
#define push_back emplace_back
using namespace std;
int N, M;
pii A[30005];
int dist[30005][180];
int vis[30005][180];
vector<pii> adj[30005];
vector<int> dog[30005];
void BFS() {
priority_queue<piii> pq;
memset(dist, 0x3f3f3f3f, sizeof(dist));
memset(vis, 0x3f3f3f3f, sizeof(vis));
pq.push(make_tuple(0, A[0].first, 0));
dist[A[0].first][0] = 0;
int u, mov; int trav;
while(!pq.empty()) {
tie(trav, u, mov) = pq.top();
pq.pop();
if(dist[u][mov] < trav || vis[u][mov] <= trav) continue;
if(mov != 0) {
if(u - mov >= 0 && trav + 1 < dist[u - mov][mov]) {
dist[u - mov][mov] = trav + 1;
pq.push(make_tuple(trav + 1, u - mov, mov));
}
if(u + mov <= N && trav + 1 < dist[u + mov][mov]) {
dist[u + mov][mov] = trav + 1;
pq.push(make_tuple(trav + 1, u + mov, mov));
}
if(dist[u][0] > trav) {
dist[u][0] = trav;
pq.push(make_tuple(trav, u, 0));
}
}else {
int v, w;
for(pii now : adj[u]) {
v = now.first, w = now.second + trav;
if(w < dist[v][0]) {
dist[v][0] = w;
pq.push(make_tuple(w, v, 0));
}
}
for(int v : dog[u]) {
if(trav < dist[u][v]) {
dist[u][v] = trav;
pq.push(make_tuple(trav, u, v));
}
}
}
vis[u][mov] = trav;
}
if(dist[A[1].first][0] == 0x3f3f3f3f) puts("-1");
else printf("%d\n", dist[A[1].first][0]);
}
int main() {
// freopen("out.txt", "w", stdout);
scanf("%d %d", &N, &M);
int pos, mov;
for(int i = 0; i < M; i++) {
scanf("%d %d", &pos, &mov);
A[i] = make_pair(pos, mov);
if(mov * mov > N) {
for(int i = pos - mov, j = 1; i >= 0; i -= mov, j++) {
adj[pos].push_back(i, j);
}
for(int i = pos + mov, j = 1; i <= N; i += mov, j++) {
adj[pos].push_back(i, j);
}
}else {
dog[pos].push_back(mov);
}
}
BFS();
}
