#include "bits/stdc++.h"
using namespace std;
const int MAXN = 30007;
const int MAXM = 30007;
const int INF_INT = 2147483647;
int n,m;
vector<int> arr[MAXN];
int power[MAXM];
vector<vector<int>> dist(MAXM,vector<int>(MAXN));
deque<pair<int,int>> dq;
bool seenposition[MAXN];
int main() {
#ifdef LOCAL
freopen("submission/input.in", "r", stdin);
freopen("submission/output.out", "w", stdout);
#else
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
cin >> n >> m;
int start,end;
for (int i = 1; i<=m; i++) for (int j = 1; j<=n; j++) dist[i][j] = INF_INT;
for (int i = 0; i<m; i++) {
int x; cin >> x >> power[i];
if (i == 0) start = x;
if (i == 1) end = x;
arr[x].push_back(i);
}
dq.push_back({0,start});
dist[0][start] = 0;
int jumps = -1;
while (!dq.empty()) {
int x = dq.front().first, y = dq.front().second; dq.pop_front();
if (0<=y-power[x] && dist[x][y]+1<dist[x][y-power[x]]) {
dist[x][y-power[x]] = dist[x][y]+1;
dq.push_back({x,y-power[x]});
}
if (y+power[x]<n && dist[x][y]+1<dist[x][y+power[x]]) {
dist[x][y+power[x]] = dist[x][y]+1;
dq.push_back({x,y+power[x]});
}
if (seenposition[y]) continue;
seenposition[y] = true;
if (end == y) {
jumps = dist[x][y]; break;
}
for (int i : arr[y]) {
if (i == x) continue;
dist[i][y] = dist[x][y]; dq.push_front({i,y});
}
}
cout << jumps << '\n';
return 0;
}
