//LaziChicken - 9/2023
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pli pair <ll, int>
#define pil pair <int, ll>
#define fi first
#define se second
#define dim 3
#define tii tuple <int, int, int>
#define inf 0x3f
const ll nx = 3e4+2;
const ll bx = 1e3+2;
const ll mod = 1e9+7;
//--------------------------------
int n, m, sq, st, ed, res = 1e9;
int dist[nx][103];
bool check[nx];
priority_queue <tii, vector<tii>, greater<tii>> pq;
vector <int> point[nx];
void dijkstra(){
while(pq.size()){
int val, u, x;
tie(val, u, x) = pq.top();
// cerr << val << " " << u << " " << x << "\n";
pq.pop();
if (dist[u][x] != val) continue;
if (u == ed){
cout << val; exit(0);
}
if (x){
if (u - x >= 0 and dist[u-x][x] > val + 1){
pq.emplace(dist[u-x][x] = val + 1, u - x, x);
// cerr << "PUT: " << val + 1 << " " << u - x << " " << x << "\n";
}
if (u + x < n and dist[u+x][x] > val + 1){
pq.emplace(dist[u+x][x] = val + 1, u + x, x);
// cerr << "PUT: " << val + 1 << " " << u + x << " " << x << "\n";
}
}
if (check[u]) continue;
check[u] = 1;
for (auto p : point[u]){
if (p >= sq){
for (int i = 1; u - i * p >= 0 or u + i * p < n; i++){
if (u - i * p >= 0 and dist[u-i*p][0] > val + i){
pq.emplace(dist[u-i*p][0] = val + i, u - i * p, 0);
// cerr << "PUT: " << val + i << " " << u - i * p << " " << 0 << "\n";
}
if (u + i * p < n and dist[u+i*p][0] > val + i){
pq.emplace(dist[u+i*p][0] = val + i, u + i * p, 0);
// cerr << "PUT: " << val + i << " " << u + i * p << " " << 0 << "\n";
}
}
}
else{
if (u - p >= 0 and dist[u-p][p] > val + 1){
pq.emplace(dist[u-p][p] = val + 1, u - p, p);
// cerr << "PUT: " << val + 1 << " " << u - p << " " << p << "\n";
}
if (u + p < n and dist[u+p][p] > val + 1){
pq.emplace(dist[u+p][p] = val + 1, u + p, p);
// cerr << "PUT: " << val + 1 << " " << u + p << " " << p << "\n";
}
}
}
}
}
//--------------------------------
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0, b, p; i < m; i++){
cin >> b >> p;
if (i == 0) st = b;
if (i == 1) ed = b;
point[b].emplace_back(p);
}
sq = sqrt(n);
memset(dist, inf, sizeof(dist));
dist[st][0] = 0;
pq.emplace(0, st, 0);
dijkstra();
cout << -1;
}
/*
Note:
*/
