//Sorry but iam targeting IOI :))
//NEVER LOSE HOPE
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define endl "\n"
#define ceil(a,b) (a+(b-1))/b
#define all(v) v.begin(),v.end()
#define Hidden ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N=3e4+10,mod = 1e9+7;
int n,m,f[N],dis[N];
pair<int,int>a[N];
vector<pair<int,int>>adj[N];
int main(){
Hidden;
cin>>n>>m;
for(int i=0;i<m;++i){
cin>>a[i].first>>a[i].second;
f[a[i].first]++;
}
for(int i=0;i<m;++i){
for(int j=a[i].first+a[i].second;j<=n;j+=a[i].second){
if(!f[j]) continue;
adj[a[i].first].push_back({j,((j-a[i].first)/a[i].second)});
}
for(int j=a[i].first-a[i].second;j>=0;j-=a[i].second){
if(!f[j]) continue;
adj[a[i].first].push_back({j,((a[i].first-j)/a[i].second)});
}
}
priority_queue<pair<int,int>>pq;
pq.push({0,a[0].first});
for(int i=0;i<N;++i) dis[i]=INT_MAX;
dis[a[0].first]=0;
while(!pq.empty()){
pair<int,int>p=pq.top();
pq.pop();
int u=p.second;
for(auto i:adj[u]){
int cost=dis[u]+i.second;
if(cost<dis[i.first]){
dis[i.first]=cost;
pq.push({-cost,i.first});
}
}
}
if(dis[a[1].first]==INT_MAX) cout<<"-1\n";
else cout<<dis[a[1].first]<<'\n';
}
