#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
const int N = 30005;
vector<pair<ll,ll>>G[N];
vector<ll>dist(N,1e18),par(N,-1);
vector<int> jump[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<pair<int,int>> a(m);
for(int i = 0; i < m; i++) {
cin >> a[i].first >> a[i].second;
jump[a[i].first].push_back(a[i].second);
}
for(int i = 0; i < n; i++) {
for(auto it : jump[i]) {
int cnt = 1;
for(int j = i - it; j >= 0; j -= it) {
G[i].push_back({j, cnt});
cnt += 1;
}
cnt = 1;
for(int j = i + it; j < n; j += it) {
G[i].push_back({j, cnt});
cnt += 1;
}
}
}
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;
pq.push({0,a[0].first});
dist[a[0].first] = 0;
vector<bool>vis(n+1,false);
while(pq.size()) {
ll d,u;
tie(d,u) = pq.top();
pq.pop();
if(vis[u]) continue;
vis[u] = true;
for(auto X:G[u]) {
if(dist[X.first] > dist[u] + X.second) {
dist[X.first] = dist[u] + X.second;
pq.push({dist[X.first],X.first});
par[X.first] = u;
}
}
}
if(dist[a[1].first] == 1e18) {
cout << - 1;
}
else {
cout << dist[a[1].first];
}
}
