#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;
int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
int n,m;cin>>n>>m;
vector<set<int>> b(n);
int s,e;
REP(i,0,m){
int x,y;cin>>x>>y;
if(i==0)s=x;
else if(i==1)e=x;
b[x].insert(y);
}
vi dist(n,inf);
dist[s]=0;
priority_queue<pi,vector<pi>,greater<pi>> pq;
pq.push({dist[s],s});
while(!pq.empty()){
int x=pq.top().F;
int y=pq.top().S;
pq.pop();
if(dist[y]<x)continue;
for(auto z:b[y]){
int tmp=z;
int c=1;
while(y+z<n){
if(dist[y+z]>x+c){
dist[y+z]=x+c;
pq.push({dist[y+z],y+z});
}
z+=tmp;
c++;
}
z=tmp;c=1;
while(y-z>=0){
if(dist[y-z]>x+c){
dist[y-z]=x+c;
pq.push({dist[y-z],y-z});
}
z+=tmp;
c++;
}
}
}
int ans=dist[e];
if(ans==inf)cout<<-1;
else cout<<ans;
}
