#include <bits/stdc++.h>
typedef int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=3e4+100,sq=173;
ll dis[N][sq];
set <pair <pii,int> > s;
vector <int> a[N];
ll p[N];
void dij(){
while(s.size()){
pii v=s.begin()->F;
ll w=dis[v.F][v.S];
s.erase(s.begin());
// cout << v.F << " " << v.S << " " << w << endl;
if (v.S==0){
for (auto e : a[v.F]){
ll u=p[e];
//cout << u << endl;
if (u<sq){
if (dis[v.F][u]>w){
s.erase({{v.F,u},dis[v.F][u]});
dis[v.F][u]=w;
s.insert({{v.F,u},dis[v.F][u]});
}
}
else{
for (int i=-v.F/u;i<=N/sq;i++){
ll h=v.F+i*u;
if (h>=0 && h<N){
if (dis[h][0]>w+abs(i)){
s.erase({{h,0},dis[h][0]});
dis[h][0]=w+abs(i);
s.insert({{h,0},dis[h][0]});
}
}
}
}
}
continue;
}
ll u=v.S;
ll h=v.F+u;
if (h>=0 && h<N && dis[h][0]>w+1){
s.erase({{h,0},dis[h][0]});
dis[h][0]=w+1;
s.insert({{h,0},dis[h][0]});
}
if (h>=0 && h<N && dis[h][u]>w+1){
s.erase({{h,u},dis[h][u]});
dis[h][u]=w+1;
s.insert({{h,u},dis[h][u]});
}
h=v.F-u;
if (h>=0 && h<N && dis[h][0]>w+1){
s.erase({{h,0},dis[h][0]});
dis[h][0]=w+1;
s.insert({{h,0},dis[h][0]});
}
if (h>=0 && h<N && dis[h][u]>w+1){
s.erase({{h,u},dis[h][u]});
dis[h][u]=w+1;
s.insert({{h,u},dis[h][u]});
}
}
}
ll ja[N];
int32_t main(){
sync;
ll n,m;
cin >> n >> m;
for (int i=0;i<m;i++){
ll x;
cin >> x >> p[i];
a[x].pb(i);
ja[i]=x;
}
for (int i=0;i<N;i++){
for (int j=0;j<sq;j++){
dis[i][j]=2e8;
}
}
dis[ja[0]][0]=0;
s.insert({{ja[0],0},0});
dij();
ll x=ja[1];
if (dis[x][0]>1e8) kill(-1);
kill(dis[x][0]);
}
