#include<bits/stdc++.h>
using namespace std;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
typedef long long llong;
const int MAXN = 3e4 + 10;
const int INF = 1e9 + 10;
struct Edge
{
int to;
int cost;
Edge(){};
Edge(int to, int cost)
{
this->to = to;
this->cost = cost;
}
friend bool operator<(const Edge &e1, const Edge &e2)
{
return e1.cost > e2.cost;
}
};
int n, m;
int power[MAXN];
int pos[MAXN];
int dist[MAXN];
vector < Edge > adj[MAXN];
map < int, int > pows[MAXN];
void read()
{
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
cin >> pos[i] >> power[i];
pos[i]++;
}
}
void build_graph()
{
for(int i = 1; i <= m; i++)
{
pows[pos[i]][power[i]]++;
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(i == j)
continue;
int diff = abs(i - j);
set < int > dels;
for(int d = 1; d * d <= diff; d++)
{
if(diff % d == 0)
{
dels.insert(d);
dels.insert(diff / d);
}
}
for(int d : dels)
{
int len = diff / d;
if(pows[i][len])
{
adj[i].push_back(Edge(j, d));
break;
}
}
}
}
}
void solve()
{
for(int i = 1; i <= n; i++)
{
dist[i] = INF;
}
priority_queue < Edge > pq;
dist[pos[1]] = 0;
pq.push(Edge(pos[1], 0));
while(!pq.empty())
{
Edge t = pq.top();
pq.pop();
int u = t.to;
if(u == pos[2])
break;
if(t.cost > dist[u])
continue;
for(Edge &e : adj[u])
{
if(dist[e.to] > dist[u] + e.cost)
{
dist[e.to] = dist[u] + e.cost;
pq.push(Edge(e.to, dist[e.to]));
}
}
}
if(dist[pos[2]] == INF)
{
cout << -1 << endl;
}
else
{
cout << dist[pos[2]] << endl;
}
}
int main()
{
speed();
read();
build_graph();
solve();
return 0;
}
