#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
int B[30000], P[30000];
vector<int> A[30000];
int vis[2000][30001];
int main() {
int N, M; cin >> N >> M;
for(int i = 0; i < M; i++) {
cin >> B[i] >> P[i];
A[B[i]].push_back(i);
}
int ans = -1;
deque<pair<int, int> > Q;
Q.push_back({B[0], M});
vis[B[0]][M] = 1;
while(!Q.empty()) {
auto it = Q.front(); Q.pop_front();
int i = it.first, j = it.second;
if(i == B[1]) {
ans = vis[i][j];
break;
}
if(j == M) {
for(int k: A[i]) {
if(!vis[i][k]) {
vis[i][k] = vis[i][j];
Q.push_front({i, k});
}
}
}
else {
if(i - P[j] >= 0 && !vis[i - P[j]][j]) {
vis[i - P[j]][j] = vis[i][j] + 1;
Q.push_back({i - P[j], j});
}
if(i + P[j] < N && !vis[i + P[j]][j]) {
vis[i + P[j]][j] = vis[i][j] + 1;
Q.push_back({i + P[j], j});
}
if(!vis[i][M]) {
vis[i][M] = vis[i][j];
Q.push_front({i, M});
}
}
}
if(ans != -1) ans -= 1;
cout << ans << endl;
}
