#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];
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);
dists[i] = 1000000000;
}
for (int i = 0; i < m; i++)
{
int jumpCount = -1;
for (int j = positions[i]; j < n; j+=powers[i])
{
jumpCount++;
for (auto k : doges[j])
{
graph[i].push_back({k, jumpCount});
}
}
jumpCount = 0;
for (int j = positions[i]-powers[i]; j >= 0; j-=powers[i])
{
jumpCount++;
for (auto k : doges[j])
{
graph[i].push_back({k, jumpCount});
}
}
}
q.push({0, 0});
dists[0] = 0;
while (!q.empty())
{
int x = q.top().second;
//cout << "At node " << x << " which is " << dists[x] << " away\n";
if (x == 1)
{
int ans = dists[1];
cout << ans << "\n";
return 0;
}
q.pop();
if (visited[x])
{
continue;
}
visited[x] = true;
for (auto i : graph[x])
{
//cout << "Looking at node " << i.first << "\n";
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 << "Adding to queue, distance " << dists[i.first] << "away\n";
}
}
}
cout << "-1\n";
}
