#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N = 150, inf = 1e9 + 7; //
#define node pair<pair<int, int>, int>
#define mode first.first
#define a first.second
#define b second
int n, m;
int f(node i){
if (i.mode == 0) return n * i.a + i.b;
else return N * i.a + i.b / N;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
int x[m], d[m];
bitset<200 * 30000> vis[2]{};
int dis[2][200 * 30000];
vector<int> on[n];
for (int i = 0; i < m; i++){
cin >> x[i] >> d[i];
on[x[i]].push_back(i);
}
deque<node> q;
if (d[0] < N) q.push_back({{0, d[0]}, x[0]});
else q.push_back({{1, 0}, x[0]});
vis[d[0] < N ? 0 : 1][f(q.front())] = true;
while (!q.empty()){
node u = q.front();
q.pop_front();
//cout << dis[u] << ' ' << u.a << ' ' << u.b << ' ' << '\n';
if (u.mode == 0){
if (u.b + u.a < n and !vis[0][f({{0, u.a}, u.b + u.a})]){
q.push_back({{0, u.a}, u.b + u.a});
dis[0][f({{0, u.a}, u.b + u.a})] = dis[0][f(u)] + 1;
vis[0][f({{0, u.a}, u.b + u.a})] = true;
}
if (u.b - u.a >= 0 and !vis[0][f({{0, u.a}, u.b - u.a})]){
q.push_back({{0, u.a}, u.b - u.a});
dis[0][f({{0, u.a}, u.b - u.a})] = dis[0][f(u)] + 1;
vis[0][f({{0, u.a}, u.b - u.a})] = true;
}
}
else {
if (u.b + d[u.a] < n and !vis[1][f({{1, u.a}, u.b + d[u.a]})]){
q.push_back({{1, u.a}, u.b + d[u.a]});
dis[1][f({{1, u.a}, u.b + d[u.a]})] = dis[1][f(u)] + 1;
vis[1][f({{1, u.a}, u.b + d[u.a]})] = true;
}
if (u.b - d[u.a] >= 0 and !vis[1][f({{1, u.a}, u.b - d[u.a]})]){
q.push_back({{1, u.a}, u.b - d[u.a]});
dis[1][f({{1, u.a}, u.b - d[u.a]})] = dis[1][f(u)] + 1;
vis[1][f({{1, u.a}, u.b - d[u.a]})] = true;
}
}
while (!on[u.b].empty()){
int v = on[u.b].back();
on[u.b].pop_back();
if (d[v] < N and !vis[0][f({{0, d[v]}, u.b})]){
dis[0][f({{0, d[v]}, u.b})] = dis[u.mode][f(u)];
vis[0][f({{0, d[v]}, u.b})] = true;
q.push_front({{0, d[v]}, u.b});
}
else if (d[v] >= N and !vis[1][f({{1, v}, u.b})]){
dis[1][f({{1, v}, u.b})] = dis[u.mode][f(u)];
vis[1][f({{1, v}, u.b})] = true;
q.push_front({{1, v}, u.b});
}
}
if (u.b == x[1]){
cout << dis[u.mode][f(u)];
return 0;
}
}
cout << -1;
}
