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