#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define MAX 2000
int n, m, b[MAX + 3], p[MAX + 3], vis[MAX + 3][MAX + 3], opt[MAX + 3][MAX + 3], destino, res;
vector < int > v[MAX];
queue < pair < int, pair < int, int > > > q;
void salta(int largo, int pos, int salto){
if(pos < n && pos >= 0 && !vis[pos][salto]){
q.push({largo + 1, {pos, salto}});
vis[pos][salto] = 1;
opt[pos][salto] = largo;
}
}
int main(){
cin >> n >> m;
rep(i, 0, m - 1){
cin >> b[i] >> p[i];
v[b[i]].push_back(i);
}
res = -1;
destino = b[1];
vis[b[0]][p[0]] = 1;
opt[b[0]][p[0]] = 0;
q.push({0, {b[0], p[0]}});
while(!q.empty()){
int largo = q.front().first;
int pos = q.front().second.first;
int salto = q.front().second.second;
q.pop();
if(pos == destino){
res = largo;
break;
}
salta(largo, pos + salto, salto);
salta(largo, pos - salto, salto);
for(auto s: v[pos]){
salta(largo, pos + p[s], p[s]);
salta(largo, pos - p[s], p[s]);
}
}
cout << res;
return 0;
}
