#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=5e4+10,LN=30,SQ=550,M=1e5+10;
const ll INF=1e15;
const int MOD=1000000007 /*998244353*/;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
ll ans=1;
while (y != 0) {
if (y & 1) ans = ans * x % mod;
y >>= 1;
x = x * x % mod;
}
return ans;
}
ll n,m,s,t,h[N];
vector<ll> adj[N];
priority_queue<pll> q;
int main(){
fast_io;
cin >> n >> m;
for(ll i=0; i<m; i++){
ll b,p;
cin >> b >> p;
if(i==0) s=b;
if(i==1) t=b;
adj[b].push_back(p);
}
memset(h,63,sizeof h);
h[s]=0;
q.push({0,s});
while(!q.empty()){
ll v=q.top().S,x=-q.top().F;
q.pop();
if(h[v]<x) continue;
for(ll t : adj[v]){
for(ll u=v-t,j=1; u>=0; u-=t,j++){
if(h[u]<=x+j) continue;
h[u]=x+j;
q.push({-h[u],u});
}
for(ll u=v+t,j=1; u<n; u+=t,j++){
if(h[u]<=x+j) continue;
h[u]=x+j;
q.push({-h[u],u});
}
}
}
if(h[t]<=INF) cout << h[t] << '\n';
else cout << -1 << '\n';
return 0;
}
