#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
const int maxn = (int)2e3+10;
const ll LINF = (ll)1e18;
int n, m, ans;
pair<int,int> a[maxn];
vector<pii> adj[maxn];
queue<pair<int,int>> Q;
vector<int> doge[maxn];
bool vis[maxn][maxn];
int dis[maxn][maxn];
void chk(int s, int p, int s2, int p2){
if(s>=n or s<0 or vis[s][p]) return;
vis[s][p] = 1; dis[s][p] = dis[s2][p2]+1; Q.push({s,p});
}
void bfs(int pos, int power){
Q.push({pos,power});
for(int i = 0; i < maxn; i++)
for(int j = 0; j < maxn; j++)
dis[i][j]=LINF, vis[i][j]=0;
dis[pos][power]=0; vis[pos][power]=1;
while(!Q.empty()){
int s = Q.front().fi, p = Q.front().se; Q.pop();
chk(s+p,p,s,p), chk(s-p,p,s,p);
for(auto u : doge[s]) chk(s+u,u,s,p), chk(s-u,u,s,p);
}
}
int32_t main() {
cin >> n >> m; ans = LINF;
for(int i = 0; i < m; i++) cin >> a[i].fi >> a[i].se, doge[a[i].fi].pb(a[i].se);
vector<int> ord(m); iota(ord.begin(),ord.end(),0);
sort(ord.begin(),ord.end(),[&](int i, int j){ return a[i].fi < a[j].fi; });
bfs(a[0].fi, a[0].se);
for(int i = 1; i <= 2000; i++) ans = min(ans, dis[a[1].fi][i]);
if(ans==LINF) ans=-1; cout << ans;
}
