#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double
const ll N = 5e5;
const ll INF = 4e18;
const ll MOD = 1e9 + 7;
map<pii, bool> vis[2];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc = 1;
// cin >> tc;
for(;tc--;){
ll n, m; cin >> n >> m;
vector<ll> b(m + 5), p(m + 5);
for(int i = 1; i <= m; i++) cin >> b[i] >> p[i];
vector<pii> adj[n + 5];
for(int i = 1; i <= m; i++){
ll cur = 0;
for(int j = b[i] + p[i]; j < n; j += p[i]){
if(vis[0][{j, p[i]}]) break;
vis[0][{j, p[i]}] = 1;
adj[b[i]].push_back({j, ++cur});
}
cur = 0;
for(int j = b[i] - p[i]; j >= 0; j -= p[i]){
if(vis[1][{j, p[i]}]) break;
vis[1][{j, p[i]}] = 1;
adj[b[i]].push_back({j, ++cur});
}
}
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<ll> dp(n + 5, INF);
dp[b[1]] = 0;
pq.push({dp[b[1]], b[1]});
for(;!pq.empty();){
auto [dist, idx] = pq.top(); pq.pop();
if(dist > dp[idx]) continue;
for(auto [i, j] : adj[idx]){
if(dp[i] > dist + j){
dp[i] = dist + j;
pq.push({dp[i], i});
}
}
}
cout << (dp[b[2]] == INF ? -1 : dp[b[2]]) << "\n";
}
}
/*
*/
