#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, b, p;
vector<int> doges[50000];
int matrix[3000][3000];
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
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);
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
matrix[i][j] = 1000000009;
}
dists[i] = 1000000000;
}
for (int i = 0; i < m; i++)
{
int jumpCount = -1;
for (int j = positions[i]; j < n; j+=powers[i])
{
jumpCount++;
matrix[positions[i]][j] = min(matrix[positions[i]][j], jumpCount);
}
jumpCount = 0;
for (int j = positions[i]-powers[i]; j >= 0; j-=powers[i])
{
jumpCount++;
matrix[positions[i]][j] = min(matrix[positions[i]][j], jumpCount);
}
}
/*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 (int i = 0; i < n; i++)
{
if (!visited[i] and dists[x] + matrix[x][i] < dists[i])
{
dists[i] = dists[x] + matrix[x][i];
q.push({-dists[i], i});
//cout << "Pushing " <<
}
}
}
cout << "-1\n";
}
