#include <bits/stdc++.h>
using namespace std;
const int k = 300;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int n, m;
cin >> n >> m;
vector<pair<int, int>> vpii(m);
for (auto &a : vpii) cin >> a.first >> a.second;
vector<vector<int>> dp(n, vector<int>(k, INT_MAX)), out(n);
for (int i = 0; i < m; i++) out[vpii[i].first].push_back(i);
// steps, cur, power
priority_queue<array<int, 3>> pqpii;
pqpii.push({0, vpii[0].first, 0});
while (!pqpii.empty()) {
auto [steps, cur, power] = pqpii.top();
pqpii.pop();
steps = -steps;
if (dp[cur][power] <= steps) continue;
dp[cur][power] = steps;
if (dp[cur][0] > steps || power == 0) {
dp[cur][0] = steps;
for (auto a : out[cur])
if (vpii[a].second >= k) {
for (int i = cur % vpii[a].second; i < n; i += vpii[a].second) {
int news = steps + abs(i - cur) / vpii[a].second;
if (i != cur && dp[i][0] == INT_MAX) {
pqpii.push({-news, i, 0});
}
}
} else {
dp[cur][vpii[a].second] = steps;
int newr = cur + vpii[a].second;
if (newr < n && dp[newr][vpii[a].second] == INT_MAX) {
pqpii.push({-steps - 1, newr, vpii[a].second});
}
int newl = cur - vpii[a].second;
if (newl >= 0 && dp[newl][vpii[a].second] == INT_MAX) {
pqpii.push({-steps - 1, newl, vpii[a].second});
}
}
}
if (power != 0) {
int newr = cur + power;
if (newr < n && dp[newr][power] == INT_MAX) {
pqpii.push({-steps - 1, newr, power});
}
int newl = cur - power;
if (newl >= 0 && dp[newl][power] == INT_MAX) {
pqpii.push({-steps - 1, newl, power});
}
}
}
int x = dp[vpii[1].first][0];
if (x == INT_MAX) {
cout << "-1\n";
} else {
cout << x << "\n";
}
}
