#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int MAXN=3e4+5;
const int sqr=222;
int dp[MAXN];
bool ck[MAXN][sqr+5];
vector<int> vi[MAXN];
priority_queue< ii,vector<ii>,greater<ii> > pq;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,st=0,ed=0;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int b,p;
cin>>b>>p;
if(i==1) st=b;
if(i==2) ed=b;
vi[b].push_back(p);
}
for(int i=0;i<n;i++) dp[i]=1e9;
pq.push({dp[st]=0,st});
while(!pq.empty())
{
int a=pq.top().fi,b=pq.top().se;
pq.pop();
if(dp[b]<a) continue;
for(auto v:vi[b])
{
if(v<=sqr) ck[b][v]=true;
int pos=b,cnt=0;
while(pos+v<n)
{
pos+=v,cnt++;
if(v<=sqr&&ck[pos][v]) break;
if(dp[pos]>a+cnt) pq.push({dp[pos]=a+cnt,pos});
if(v<=sqr) ck[pos][v]=true;
}
pos=b,cnt=0;
while(pos-v>=0)
{
pos-=v,cnt++;
if(v<=sqr&&ck[pos][v]) break;
if(dp[pos]>a+cnt) pq.push({dp[pos]=a+cnt,pos});
if(v<=sqr) ck[pos][v]=true;
}
}
}
if(dp[ed]==1e9) cout<<-1;
else cout<<dp[ed];
}
