// tle
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
// #define F first
// #define S second
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
int N, M;
cin >> N >> M;
vector<int> S(M), P(M); // doge start, doge power
vector<vector<int>> B(N); // building -> doge inside
FOR(i, M) {
cin >> S[i] >> P[i];
B[S[i]].push_back(i);
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // jumps, building
vector<int> vis(N, 1e9);
pq.push({0,S[0]});
int found = -1e9;
while(pq.size()) {
auto [j, u] = pq.top();
pq.pop();
if (vis[u] <= j) continue;
if (u == S[1]) {found = j; break;}
vis[u] = j;
for(int d: B[u]) {
for(int m = -(u/P[d]); m <= (N-u-1)/P[d]; m++) {
// if (u+m*P[d] < 0 || u+m*P[d] >= N) continue;
pq.push({j+abs(m), u+m*P[d]});
}
}
}
if (found != -1e9) cout << found;
else cout << -1;
}
