#include<bits/stdc++.h>
#define ll int
#define ff first
#define ss second
using namespace std;
ll n,m,i,j,b[30005],p[30005],x,y;
vector<ll> v[30005];
set<pair<ll,ll>> q;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
vector<ll> dist(n,1e9);
for(i=0;i<m;i++){
cin >> b[i] >> p[i];
v[b[i]].push_back(p[i]);
}
dist[b[0]]=0;
q.insert({0,b[0]});
while(!q.empty()){
pair<ll,ll> z=*q.begin();
x=z.ss;
y=z.ff;
q.erase(q.begin());
for(ll i:v[x]){
ll b,p;
p=0;
for(b=x;b<n;b+=i){
if(dist[b]>y+p){
if(dist[b]<1e9) q.erase({dist[b],b});
dist[b]=y+p;
q.insert({dist[b],b});
}
p++;
}
p=0;
for(b=x;b>=0;b-=i){
if(dist[b]>y+p){
if(dist[b]<1e9) q.erase({dist[b],b});
dist[b]=y+p;
q.insert({dist[b],b});
}
p++;
}
}
}
if(dist[b[1]]!=1e9) cout << dist[b[1]];
else cout << -1;
}
