/** author : _RAIN_ **/
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using ui64 = unsigned long long;
#define MASK(x) ((i64)(1) << (x))
#define BIT(mask , x) (((mask) >> (x)) & (1))
template<class T>
bool maximize(T &a , T b) {if (a < b) return a = b , true; else return false;}
template<class T>
bool minimize(T &a , T b) {if (a > b) return a = b , true; else return false;}
template<class T>
T gcd(T x , T y) {while (y) swap(y , x %= y); return x;}
template<class T>
T lcm(T x , T y) {return (x * y) / gcd(x , y);}
const int maxn = 3e4;
int b[maxn + 2] , p[maxn + 2] , idx[maxn + 2];
int n , numperson;
namespace subtask1
{
bool check()
{
return n <= (int)2e3 && numperson <= (int)2e3;
}
const int N = (int)2e3;
int cost[N + 2][N + 2];
int d[N + 2] ;
vector<int> g[N + 2];
void main_code(void)
{
memset(cost , 0x3f , sizeof cost);
memset(d , 0x3f , sizeof d);
for (int i = 1; i <= numperson; ++i)
{
for (int j = 1; j <= numperson; ++j)
{
if (b[i] != b[j])
{
int dist = abs(b[i] - b[j]);
if (dist % p[i] == 0)
{
g[b[i]].emplace_back(b[j]);
minimize(cost[b[i]][b[j]] , dist / p[i]);
}
if (dist % p[j] == 0)
{
g[b[j]].emplace_back(b[i]);
minimize(cost[b[j]][b[i]] , dist / p[j]);
}
}
}
}
priority_queue<pair<i64 ,int> , vector<pair<i64 , int>> , greater<pair<i64 , int>>> q;
d[b[1]] = 0;
q.emplace(d[b[1]] , b[1]);
while (q.size())
{
int u = q.top().second;
int val = q.top().first; q.pop();
if (val != d[u]) continue;
for (int& v : g[u])
{
if (minimize(d[v] , d[u] + cost[u][v]))
q.emplace(d[v] , v);
}
}
cout << (d[b[2]] == d[n + 1] ? -1 : d[b[2]]);
}
}
namespace subtask2
{
bool check(void)
{
return (int)n <= (int)2e3;
}
const int N = (int)2e3;
vector<int> g[N + 2];
vector<int> divisor[N + 2];
int cost[N + 2][N + 2];
bool ok[N + 2][N + 2];
int d[N + 2];
void prepare(void)
{
for (int i = 1; i <= numperson; ++i)
ok[b[i]][p[i]] = true;
for (int i = 1; i <= trunc(sqrt(N)); ++i)
{
divisor[i * i].emplace_back(i);
for (int j = i + 1; j <= N / i; ++j)
{
divisor[i * j].emplace_back(i);
divisor[i * j].emplace_back(j);
}
}
for (int i = 1; i <= N; ++i) sort(divisor[i].begin() , divisor[i].end() , greater<int>());
return;
}
void main_code(void)
{
prepare();
memset(cost , 0x3f , sizeof cost);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (i != j)
{
int dist = abs(i - j);
for (auto& v : divisor[dist])
{
if (ok[i][v])
{
g[i].emplace_back(j);
cost[i][j] = dist / v;
break;
}
}
for (auto& v : divisor[dist])
{
if (ok[j][v])
{
g[j].emplace_back(i);
cost[j][i] = dist / v;
break;
}
}
}
}
}
memset(d , 0x3f , sizeof d);
priority_queue<pair<i64 ,int> , vector<pair<i64 , int>> , greater<pair<i64 , int>>> q;
d[b[1]] = 0;
q.emplace(d[b[1]] , b[1]);
while (q.size())
{
int u = q.top().second;
int val = q.top().first; q.pop();
if (val != d[u]) continue;
for (int& v : g[u])
{
if (minimize(d[v] , d[u] + cost[u][v]))
q.emplace(d[v] , v);
}
}
cout << (d[b[2]] == d[n + 1] ? -1 : d[b[2]]);
}
}
namespace subtask3
{
bool check(void)
{
return true;
}
const int N = 3e4;
const int maxnude = 2e3;
const int lim = 300;
vector<int> g[N + 2];
int d[N + 2][lim + 6];
int dist[N + 2][lim + 6];
#define Val(x) get<0>(x)
#define Node(x) get<1>(x)
#define Add(x) get<2>(x)
void main_code(void)
{
memset(dist , 0x3f , sizeof dist);
for (int i = 1; i <= numperson; ++i)
g[b[i]].emplace_back(p[i]);
// if it power reach more than lim -> brute force and simple djistrak
// else take the Djistrak such as subtask 1 + 2
priority_queue<tuple<i64 , int , int> , vector<tuple<i64 , int , int>> , greater<tuple<i64 , int , int>>> q;
if (p[1] <= lim) dist[b[1]][p[1]] = 0 , q.emplace(dist[b[1]][p[1]] , b[1] , p[1]);
else dist[b[1]][lim + 1] = 0 , q.emplace(dist[b[1]][lim + 1] , b[1] , lim + 1);
while (q.size())
{
tuple<int , int , int> res = q.top(); q.pop();
int val = Val(res);
int u = Node(res);
int p = Add(res);
if (val != dist[u][p]) continue;
if (p <= lim)
{
if (u + p < n && minimize(dist[u + p][p] , dist[u][p] + 1))
q.emplace(dist[u + p][p] , u + p , p);
if (u - p >= 0 && minimize(dist[u - p][p] , dist[u][p] + 1))
q.emplace(dist[u - p][p] , u - p , p);
}
for (auto& add : g[u])
{
if (add <= lim)
{
if (minimize(dist[u][add] , dist[u][p]))
q.emplace(dist[u][add] , u, add);
}
if (add > lim)
{
for (int v = u , cnt = 0; v < n; v += add , cnt++)
if (minimize(dist[v][lim + 1] , dist[u][p] + cnt))
q.emplace(dist[v][lim + 1] , v , lim + 1);
for (int v = u , cnt = 0; v >= 0; v -= add , cnt++)
if (minimize(dist[v][lim + 1] , dist[u][p] + cnt))
q.emplace(dist[v][lim + 1] , v , lim + 1);
}
}
g[u].clear();
}
int answer = dist[n][0];
for (int i = 0 ; i <= lim + 1; ++i)
minimize(answer , dist[b[2]][i]);
if (answer == dist[n][0]) answer = -1;
cout << answer;
return;
}
}
int32_t main(void)
{
cin.tie(nullptr)->sync_with_stdio(false);
const string name = "main";
if (fopen((name + ".inp").c_str() , "r"))
{
(void)!freopen((name + ".inp").c_str() , "r" , stdin);
(void)!freopen((name + ".out").c_str() , "w+", stdout);
}
cin >> n >> numperson;
for (int i = 1; i <= numperson; ++i)
cin >> b[i] >> p[i];
if (subtask1::check())
return subtask1::main_code() , 0;
if (subtask2::check())
return subtask2::main_code() , 0;
return subtask3::main_code() , 0;
}
