#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
int n, m, b[30005], p[30005], dist[30005][N];
vector<int> v[N];
deque<tuple<int, int, int>> q;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 1;i<=m;i++){
cin >> b[i] >> p[i];
v[b[i]].push_back(i);
}
memset(dist, -1, sizeof dist);
dist[1][b[1]] = 0;
q.push_front({0, 1, b[1]});
while(!q.empty()){
auto [d, id, u] = q.front();
q.pop_front();
for(auto x : v[u]){
if(dist[x][u] == -1){
dist[x][u] = d;
q.push_front({d, x, u});
}
}
if(u - p[id] >= 0 && dist[id][u - p[id]] == -1){
dist[id][u - p[id]] = d + 1;
q.push_back({d + 1, id, u - p[id]});
}
if(u + p[id] < n && dist[id][u + p[id]] == -1){
dist[id][u + p[id]] = d + 1;
q.push_back({d + 1, id, u + p[id]});
}
}
cout << dist[2][b[2]];
}
