#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
//using namespace __gnu_pbds;
using ll = long long;
using vi = vector<ll>;
using vvi = vector<vector<ll>>;
const ll mod = 998244353;
//using oset = tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2020;
const int B = 150;
ll n, m, dist[maxn], sqdst[maxn][B+33], s, t;
vi doges[maxn];
int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
memset(dist, 0x3f, sizeof dist);
memset(sqdst, 0x3f, sizeof sqdst);
cin >> n >> m;
for (int b, p, i = 0; i < m; i++) {
cin >> b >> p;
if(!i) s = b;
if(i==1) t = b;
doges[b].pb(p);
}
priority_queue<pair<int, int>> pq;
dist[s]=0;
pq.push({0, s});
while (!pq.empty()) {
int u, cst;
tie(cst, u) = pq.top();
pq.pop();
cst *= -1;
if (cst > dist[u])
continue;
if(u==t) {
cout << cst << '\n';
return 0;
}
for (auto k : doges[u]) {
if(k <= B) {
sqdst[u][k]=dist[u];
}
for (int v, ok = 1, i = 1; (k>B||ok)&&(u + i * k < n || u - i * k >= 0); i++) {
v = u + i*k;
if(k <= B) {
ok = 0;
}
if(v < n){
if(k <= B && sqdst[v][k]>=dist[u] + i) {
ok = 1;
sqdst[v][k]=dist[u] + i;
}
if(dist[v] > dist[u] + i) {
dist[v] = dist[u] + i;
pq.push({-dist[v], v});
}
}
v = u - i * k;
if(v >= 0){
if(k <= B && sqdst[v][k]>=dist[u] + i) {
ok = 1;
sqdst[v][k]=dist[u] + i;
}
if(dist[v] > dist[u] + i) {
dist[v] = dist[u] + i;
pq.push({-dist[v], v});
}
}
}
}
}
cout << -1;
}
