//https://vjudge.net/contest/802640#problem/C
#include <bits/stdc++.h>
using namespace std;
#define MAX 30303
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define __buitin_popcount __builtin_popcountll
#define BIT(x,i) (((x)>>(i))&1ll)
#define MASK(i) (1ll<<(i))
template<class X,class Y> bool maximize(X &x,Y y)
{
if(x<y)
{
x=y;
return 1;
}
return 0;
}
template<class X,class Y> bool minimize(X &x,Y y)
{
if(y<x)
{
x=y;
return 1;
}
return 0;
}
const int inf=1e9+412009;
const ll INF=2e18+412009;
const int blockSize=175;
int n,m;
int b[MAX],p[MAX];
void nhap()
{
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>b[i]>>p[i],b[i]++;
}
struct STATE
{
int u,jump;
ll dist;
STATE(int _u,int _dist,int _jump=inf)
{
u=_u;
dist=_dist;
jump=_jump;
}
bool operator < (STATE other) const
{
return dist>other.dist;
}
};
ll dp[MAX][blockSize+5];
ll f[MAX];
vector<int> val[MAX];
void solve()
{
for(int i=1;i<=m;i++) val[b[i]].push_back(i);
memset(dp,0x3f,sizeof(dp));
memset(f,0x3f,sizeof(f));
queue<STATE> pq;
f[b[1]]=0;
pq.push(STATE(b[1],0));
while(!pq.empty())
{
STATE tmp=pq.front();pq.pop();
int u=tmp.u;
ll dist=tmp.dist;
int jump=tmp.jump;
if(u==b[2]) continue;
if(jump==inf)
{
if(dist>f[u]) continue;
}
else
{
if(dist>dp[u][jump]) continue;
if(u+jump<=n&&minimize(dp[u+jump][jump],dist+1)) pq.push(STATE(u+jump,dist+1,jump));
if(u-jump>0&&minimize(dp[u-jump][jump],dist+1)) pq.push(STATE(u-jump,dist+1,jump));
}
for(int i:val[u])
{
if(p[i]<=blockSize)
{
if(!minimize(dp[u][p[i]],dist)) continue;
if(u+p[i]<=n&&minimize(dp[u+p[i]][p[i]],dist+1)) pq.push(STATE(u+p[i],dist+1,p[i]));
if(u-p[i]>0&&minimize(dp[u-p[i]][p[i]],dist+1)) pq.push(STATE(u-p[i],dist+1,p[i]));
}
else
{
for(int j=1;u+j*p[i]<=n;j++)
{
int v=u+j*p[i];
if(minimize(f[v],dist+j)) pq.push(STATE(v,dist+j));
}
for(int j=1;u-j*p[i]>0;j++)
{
int v=u-j*p[i];
if(minimize(f[v],dist+j)) pq.push(STATE(v,dist+j));
}
}
}
}
ll ans=f[b[2]];
for(int jump=0;jump<=blockSize;jump++) minimize(ans,dp[b[2]][jump]);
if(ans>=INF) cout<<-1;
else cout<<ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
nhap();
solve();
return 0;
}
