#include <iostream>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define pii pair<int, int>
#define fst first
#define snd second
#define vi vector<int>
#define vpi vector<pii>
#define pub push_back
using namespace std;
const int MX = 1e9;
int n, m, s, e, dst[30001] = {};
vpi adj[30001];
unordered_set<int> edgeQuery[30001];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int temp[30001] = {}, tpsz = 0;
inline int dijkstra()
{
pq.push({0, s});
dst[s] = 0;
while (pq.size())
{
pii dt = pq.top(); pq.pop();
if (dst[dt.snd] == dt.fst)
{
//cout << "DIK : " << dt.snd << ", " << dt.fst << "\n";
if (dt.snd == e) {return dt.fst;}
for (auto v : adj[dt.snd])
{
if (dt.fst + v.snd < dst[v.fst])
{
dst[v.fst] = dt.fst + v.snd;
pq.push({dt.fst + v.snd, v.fst});
}
}
}
}
return -1;
}
int main()
{
// ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
dst[i] = MX;
}
for (int i = 0; i < m; i++)
{
int u, t; cin >> u >> t;
edgeQuery[u].insert(t);
if (i == 0) s = u;
else if (i == 1) e = u;
}
for (int i = 0; i < n; i++)
{
while (edgeQuery[i].size())
{
int x = *edgeQuery[i].begin(), s = i % x, lst = -1, cnt = 0;
for (; s < n; s += x)
{
if (edgeQuery[s].count(x))
{
edgeQuery[s].erase(x);
if (lst >= 0)
{
adj[lst].push_back({s, cnt});
adj[s].push_back({lst, cnt});
}
lst = s; cnt = 1;
for (int i = tpsz - 1; i >= 0; i--)
{
adj[s].push_back({temp[i], cnt});
cnt++;
}
tpsz = 0;
cnt = 0;
}
else
{
if (lst >= 0)
{
adj[lst].push_back({s, cnt});
}
temp[tpsz++] = s;
}
cnt++;
}
tpsz = 0;
}
}
/*
for (int i = 0; i < n; i++)
{
cout << i << "-th node adjacency list :\n";
for (auto x : adj[i])
{
cout << x.fst << ", " << x.snd << '\n';
}
}
cout << "Here\n";
*/
cout << dijkstra() << '\n';
return 0;
}
