#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
const int MAXN = 30100;
int n, m;
int b[MAXN], p[MAXN];
vii adj[MAXN];
int d[2100][2100];
//bool vis[2100][2100];
//bool visSc[2100];
vi jumps[2100];
void bfs () {
FOR(i, 0, n) FOR(j, 0, n) d[i][j] = -1;
d[b[0]][0] = 0;
queue<pii> q;
q.push({b[0], 0});
while (!q.empty()) {
int id = q.front().f, jump = q.front().s;
q.pop();
jumps[id].pb(jump);
for (int j : jumps[id]) {
int newD = id + j;
if (newD < n && d[newD][j] == -1) {
d[newD][j] = d[id][jump] + 1;
q.push({newD, j});
}
newD = id - j;
if (newD >= 0 && d[newD][j] == -1) {
d[newD][j] = d[id][jump] + 1;
q.push({newD, j});
}
}
jumps[id].clear();
}
}
int main()
{
FAST_IO;
cin >> n >> m;
FOR(i, 0, m-1) cin >> b[i] >> p[i];
FOR(i, 0, m-1) jumps[b[i]].pb(p[i]);
bfs();
int ans = -1;
FOR(i, 0, n) {
int crD = d[b[1]][i];
if (crD == -1) continue;
if (ans == -1 || ans > crD)
ans = crD;
}
cout << ans << "\n";
return 0;
}
