#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pi 3.14159265358979323846
#define pb push_back
#define ar array
template<typename T, typename cmp = std::greater<T>>
using pq = priority_queue<T, vector<T>, cmp>;
template<typename T, typename cmp = std::less<T>>
using ordered_set = tree<T, __gnu_pbds::null_type, cmp, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
void chay()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#define task "Hi"
freopen(task".INP", "r", stdin);
freopen(task".OUT", "w", stdout);
}
const int N = 30000, INF = numeric_limits<int>::max();
const int block = 200;
const long long INFLL = numeric_limits<ll>::max();
long long M = 1e9+7;
int n, m, B[N+5], P[N+5];
int cs[block+5][N+5];
vector<ar<int,2>> adj[block*N+5];
template<typename data = ll, typename datacanh = ar<int,2>>
vector<data> dijikstra(int u, int n, vector<datacanh> adj[])
{
vector<bool> vis(n+1,false);
vector<data> d(n+1, numeric_limits<data>::max());
pq<ar<data,2>> q;
q.push({0,u});
d[u] = 0;
while (!q.empty())
{
int u = q.top()[1]; q.pop();
if (vis[u]) continue;
vis[u] = true;
for (datacanh canh : adj[u])
{
int v = canh[0];
data w = canh[1];
if (d[v] > d[u] + w)
{
d[v] = d[u] + w;
q.push({d[v],v});
}
}
}
return d;
}
void solve()
{
cin>>n>>m;
for (int i = 1; i <= m; i++)
{
cin>>B[i]>>P[i];
B[i]++;
}
int dem = 0;
for (int i = 0; i <= block; i++)
{
for (int j = 1; j <= n; j++)
{
cs[i][j] = ++dem;
}
}
for (int i = 1; i <= block; i++)
{
for (int j = 1; j <= n; j++)
{
adj[cs[i][j]].pb({cs[0][j], 0});
if (j - i >= 1) adj[cs[i][j]].pb({cs[i][j-i], 1});
if (j + i <= n) adj[cs[i][j]].pb({cs[i][j+i], 1});
}
}
for (int i = 1; i <= m; i++)
{
int ht = B[i], kc = P[i];
if (kc > block)
{
for (int vitri = ht % kc; vitri <= n; vitri += kc)
{
adj[cs[0][ht]].pb({cs[0][vitri], abs(vitri - ht) / kc});
}
}
else adj[cs[0][ht]].pb({cs[kc][ht], 0});
}
vector<int> d = dijikstra<int, ar<int,2>>(B[1], dem, adj);
if (d[B[2]] != INF) cout<<d[B[2]];
else cout<<-1;
}
signed main ()
{
//chay();
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin>>t;
while (t--)
{
solve();
}
return 0;
}
