#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 main(){
ios::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
int x[m], d[m];
map<node, bool> vis;
map<node, int> dis;
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[q.front()] = true;
int ans = inf;
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, u.a}, u.b + u.a}]){
q.push_back({{0, u.a}, u.b + u.a});
dis[{{0, u.a}, u.b + u.a}] = dis[u] + 1;
vis[{{0, u.a}, u.b + u.a}] = true;
}
if (u.b - u.a >= 0 and !vis[{{0, u.a}, u.b - u.a}]){
q.push_back({{0, u.a}, u.b - u.a});
dis[{{0, u.a}, u.b - u.a}] = dis[u] + 1;
vis[{{0, u.a}, u.b - u.a}] = true;
}
}
else {
if (u.b + d[u.a] < n and !vis[{{1, u.a}, u.b + d[u.a]}]){
q.push_back({{1, u.a}, u.b + d[u.a]});
dis[{{1, u.a}, u.b + d[u.a]}] = dis[u] + 1;
vis[{{1, u.a}, u.b + d[u.a]}] = true;
}
if (u.b - d[u.a] >= 0 and !vis[{{1, u.a}, u.b - d[u.a]}]){
q.push_back({{1, u.a}, u.b - d[u.a]});
dis[{{1, u.a}, u.b - d[u.a]}] = dis[u] + 1;
vis[{{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, d[v]}, u.b}]){
dis[{{0, d[v]}, u.b}] = dis[u];
vis[{{0, d[v]}, u.b}] = true;
q.push_front({{0, d[v]}, u.b});
}
else if (d[v] >= N and !vis[{{1, v}, u.b}]){
dis[{{1, v}, u.b}] = dis[u];
vis[{{1, v}, u.b}] = true;
q.push_front({{1, v}, u.b});
}
}
if (u.b == x[1]) ans = min(ans, dis[u]);
}
cout << (ans == inf ? -1 : ans);
}
