#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x) cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll long long
#define ull unsigned long long
#define pll pair<ll, ll>
#define pii pair<ll, ll>
#define ld long double
#define nl endl
#define tb '\t'
#define sp ' '
#define sqr(x) (x)*(x)
#define arr3 array<ll, 3>
using namespace std;
const ll MX=30002, MOD=1000000007, BLOCK=327, INF=2e9+7, LG=62;
const ll INFF=1000000000000000007;
const ld ERR=1e-6, pi=3.14159265358979323846;
ll N, M, B[MX], P[MX];
map<ll, ll> vis[MX];
vector<ll> doge[MX];
int main(){
fastio;
cin >> N >> M;
for(ll i=0; i<M; i++){
cin >> B[i] >> P[i];
doge[B[i]].pb(P[i]);
}
queue<pii> BFS;
BFS.push({B[0], P[0]});
vis[B[0]][P[0]]=0;
while(BFS.size()){
ll idx=BFS.front().fi, p=BFS.front().se, cost=vis[idx][p], j;
BFS.pop();
j=idx-p;
if(j>=0){
if(!vis[j].count(p) || vis[j][p]>cost+1){
vis[j][p]=cost+1;
BFS.push({j, p});
}
}
j=idx+p;
if(j<N){
if(!vis[j].count(p) || vis[j][p]>cost+1){
vis[j][p]=cost+1;
BFS.push({j, p});
}
}
for(ll i:doge[idx]){
if(vis[idx].count(i))
continue;
j=idx-i;
if(j>=0){
if(!vis[j].count(i) || vis[j][i]>cost+1){
vis[j][i]=cost+1;
BFS.push({j, i});
}
}
j=idx+i;
if(j<N){
if(!vis[j].count(i) || vis[j][i]>cost+1){
vis[j][i]=cost+1;
BFS.push({j, i});
}
}
}
}
ll ans=INFF;
for(ll i=0; i<=30000; i++){
if(vis[B[1]].count(i))
ans=min(ans, vis[B[1]][i]);
}
if(ans==INFF)
ans=-1;
cout << ans << nl;
}
