/*
بسم الله الرحمن الرحيم
Author:
(:Muhammad Aneeq:)
*/
#include <iostream>
#include <set>
using namespace std;
int const M=35000;
int dp[M]={};
void solve()
{
int n,m;
cin>>n>>m;
pair<int,int>a[m];
for (auto& i:a)
cin>>i.first>>i.second;
for (int i=0;i<m;i++)
dp[i]=1e9+10;
dp[0]=0;
set<pair<int,int>>s;
s.insert({0,0});
int vis[m]={};
while (s.size())
{
int i=(*begin(s)).second;
s.erase(*begin(s));
if (vis[i])
continue;
vis[i]=0;
for (int j=0;j<m;j++)
{
if (abs(a[i].first-a[j].first)%a[i].second==0&&dp[j]>dp[i]+abs(a[i].first-a[j].first)/a[i].second)
{
dp[j]=dp[i]+abs(a[i].first-a[j].first)/a[i].second;
s.insert({dp[j],j});
}
}
}
cout<<(dp[1]==1e9+10?-1:dp[1])<<endl;
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
solve();
}
