#include <iostream>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#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] = {};
vector<map<int, int>> adj;
vector<set<int>> edgeQuery;
priority_queue<pii, vector<pii>, greater<pii>> pq;
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++)
{
adj.pub(map<int, int>());
edgeQuery.pub(set<int>());
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;
}
vi temp;
for (int i = 0; i < n; i++)
{
// cout << i << "\n";
while (edgeQuery[i].size())
{
int x = *edgeQuery[i].begin(), s = i % x, lst = -1, cnt = 0;
//cout << " - " << i << " " << x << "\n";
for (; s < n; s += x)
{
if (edgeQuery[s].count(x))
{
edgeQuery[s].erase(x);
if (lst >= 0)
{
//cout << "CON " << lst << " " << s << "\n";
if (adj[lst].count(s)) adj[lst][s] = min(adj[lst][s], cnt);
else adj[lst][s] = cnt;
//cout << "CON " << s << " " << lst << "\n";
if (adj[s].count(lst)) adj[s][lst] = min(adj[s][lst], cnt);
else adj[s][lst] = cnt;
}
lst = s; cnt = 1;
for (int i = (int)temp.size() - 1; i >= 0; i--)
{
//cout << "CON " << s << " " << temp[i] << "\n";
if (adj[s].count(temp[i])) adj[s][temp[i]] = min(adj[s][temp[i]], cnt);
else {adj[s][temp[i]] = cnt;}
cnt++;
}
temp.clear();
cnt = 0;
}
else
{
if (lst >= 0)
{
//cout << "CON " << lst << " " << s << "\n";
if (adj[lst].count(s)) adj[lst][s] = min(adj[lst][s], cnt);
else adj[lst][s] = cnt;
}
temp.push_back(s);
}
cnt++;
}
temp.clear();
}
}
/*
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;
}
