#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5, INF = 2e9;
int n, m, b[N], p[N], 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);
}
for(int i = 1;i<=m;i++) for(int j = 0;j<n;j++) dist[i][j] = INF;
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] > d){
dist[x][u] = d;
q.push_front({d, x, u});
}
}
if(u - p[id] >= 0 && dist[id][u - p[id]] > d + 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]] > d + 1){
dist[id][u + p[id]] = d + 1;
q.push_back({d + 1, id, u + p[id]});
}
}
cout << dist[2][b[2]];
}
