#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>
using namespace std;
const int MAXN = 30005;
const int mod7 = 1e9+7;
const long long inf = 1e18;
vector<vector<pii>> graf(MAXN);
vector<long long> dist(MAXN, inf);
vector<vector<int>> dogos(MAXN);
set<pii> pq;
int doge0;
int doge1;
void dikstra(int nod)
{
dist[nod] = 0;
pq.insert({dist[nod], nod});
while(!pq.empty())
{
auto it = pq.begin();
int u = it-> sc;
pq.erase(it);
for(auto x: graf[u])
{
if(dist[x.fi] > dist[u] + x.sc)
{
pq.erase({dist[x.fi], x.fi});
dist[x.fi] = dist[u] + x.sc;
pq.insert({dist[x.fi], x.fi});
}
}
}
}
signed main()
{
ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
int tt=1;
//cin >> tt;
while(tt--)
{
int n,m;
cin >> n >> m;
for(int i=0; i<m; i++)
{
int a,b;cin >> a >> b;
if(i==0)doge0 = a;
if(i==1)doge1 = a;
dogos[a].pb(b);
}
for(int i=0; i<n; i++)
{
for(auto d: dogos[i])
{
int j = i;
while(j+ d <n)
{
j+=d;
graf[i].pb({j, (j-i)/d});
}
j = i;
while(j- d >=0)
{
j-=d;
graf[i].pb({j,(i-j)/d});
}
}
}
dikstra(doge0);
if(dist[doge1] == inf)cout << -1 << endl;
else cout << dist[doge1] << endl;
}
}
