//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl '\n'
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long ll;
#define int long long
const int N = 2e3+7, NN = 3e4+7, inf = 1e18;
int a[N], p[N], d[N], mark[N];
vector<int> g[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
void dij(int n){
fill(d,d+n,inf);
d[a[0]] = 0;
q.push({0,a[0]});
while(q.size()){
int v = q.top().S;
q.pop();
if (mark[v]) continue;
mark[v] = 1;
for (int p : g[v]){
for(int i=v; i<n; i+=p){
if (d[i] > d[v] + (i-v)/p){
d[i] = d[v] + (i-v)/p;
q.push({d[i],i});
}
}
for(int i=v; i; i-=p){
if (d[i] > d[v] + (v-i)/p){
d[i] = d[v] + (v-i)/p;
q.push({d[i],i});
}
}
}
}
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n,m; cin >> n >> m;
for(int i=0; i<m; i++){
cin >> a[i] >> p[i];
g[a[i]].pb(p[i]);
}
dij(n);
cout << (d[a[1]] == inf ? -1 : d[a[1]]) << endl;
return 0;
}
