#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> position;
vector<int> DP;
int minimumJumps (int l, int r, int idx, vector<bool> & visited, int jumps) {
if (idx == 1) {
return 0;
} else if (DP[idx] != -1) {
return DP[idx];
}
visited[idx] = true;
int left, right, p = position[idx];
left = idx - p;
for (int i = 1; left >= l; i++) {
if (position[left] != 0 && !visited[left]) {
jumps = min(jumps, i + minimumJumps(l, r, left, visited, jumps));
}
left -= p;
}
right = idx + p;
for (int i = 1; right <= r; i++) {
if (position[right] != 0 && !visited[right]) {
jumps = min(jumps, i + minimumJumps(l, r, right, visited, jumps));
}
right += p;
}
return DP[idx] = jumps;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m, x, p, answer;
cin >> n >> m;
position.assign(n, 0);
DP.assign(n, -1);
vector<bool> visited(n, false);
while (m--) {
cin >> x >> p;
position[x] = p;
}
answer = minimumJumps(0, n-1, 0, visited, 1e9);
if (answer == 1e9) {
cout << -1 << '\n';
} else {
cout << answer << '\n';
}
return 0;
}
