/*
بسم الله الرحمن الرحيم
Author:
(:Muhammad Aneeq:)
*/
#include <iostream>
#include <queue>
#include <vector>
#include <set>
using namespace std;
int const N=30000;
pair<int,int>a[N];
set<int>lo[N];
int dp[N];
inline void solve()
{
int n,m;
cin>>n>>m;
for (int i=0;i<m;i++)
{
cin>>a[i].first>>a[i].second;
lo[a[i].first].insert(a[i].second);
}
for (int i=0;i<n;i++)
dp[i]=1e9+10;
dp[a[0].first]=0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
pq.push({0,a[0].first});
bool vis[n]={};
while (pq.size())
{
int loc=pq.top().second;
pq.pop();
if (vis[loc])
continue;
vis[loc]=1;
for (auto j:lo[loc])
{
int z=0;
for (int k=loc-j;k>=0;k-=j)
{
z++;
if (dp[k]>dp[loc]+z)
{
dp[k]=dp[loc]+z;
pq.push({dp[k],k});
}
}
z=0;
for (int k=loc+j;k<n;k+=j)
{
z++;
if (dp[k]>dp[loc]+z)
{
dp[k]=dp[loc]+z;
pq.push({dp[k],k});
}
}
}
}
cout<<(dp[a[1].first]!=1e9+10?dp[a[1].first]:-1);
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
solve();
}
