#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, b, p;
vector<int> doges[50000];
vector<pair<int, int> > graph[50000];
int powers[50000];
int positions[50000];
priority_queue<pair<int, int> > q;
int dists[50000];
bool visited[50000];
bool visited2[3000][3000]; //position then power
set<int> powerPos[50000];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> b >> p;
powers[i] = p;
positions[i] = b;
doges[b].push_back(i);
powerPos[positions[i]].insert(powers[i]);
}
for (int i = 0; i < n; i++)
{
dists[i] = 1000000000;
}
int checkCount = 0;
for (int i = 0; i < m; i++)
{
int jumpCount = 0;
for (int j = positions[i]+powers[i]; j < n; j+=powers[i])
{
jumpCount++;
checkCount++;
graph[positions[i]].push_back({j, jumpCount});
//cout << "Connecting " << j << " to " << positions[i] << "\n";
if (powerPos[j].find(powers[i]) != powerPos[j].end())
{
break;
}
}
jumpCount = 0;
for (int j = positions[i]-powers[i]; j >= 0; j-=powers[i])
{
jumpCount++;
checkCount++;
graph[positions[i]].push_back({j, jumpCount});
//cout << "Connecting " << j << " to " << positions[i] << "\n";
if (powerPos[j].find(powers[i]) != powerPos[j].end())
{
break;
}
}
assert(checkCount < 10000000);
}
/*for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << matrix[i][j] << " ";
}
cout << "\n";
}*/
q.push({0, positions[0]});
dists[positions[0]] = 0;
while (!q.empty())
{
int x = q.top().second;
//cout << "At node " << x << " which is " << dists[x] << " away\n";
if (x == positions[1])
{
int ans = dists[positions[1]];
cout << ans << "\n";
return 0;
}
q.pop();
if (visited[x])
{
continue;
}
visited[x] = true;
for (auto i : graph[x])
{
if (!visited[i.first] and dists[x] + i.second < dists[i.first])
{
dists[i.first] = dists[x] + i.second;
q.push({-dists[i.first], i.first});
//cout << "Pushing " << i.first << " which is " << dists[i.first] << " away\n";
}
}
}
cout << "-1\n";
}
