#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;
const int inf = int(1e9)+5, maxn = int(3e4)+5;
int B[maxn], P[maxn], D[maxn][2];
vector<int> doge[maxn];
// 0 => doge
// 1 => skyscraper
bool go(int x, int y)
{
return binary_search(doge[y].begin(), doge[y].end(), P[x]);
}
int main(void)
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0;i < m;i++)
{
scanf("%d%d", &B[i], &P[i]), D[i][0] = inf;
doge[B[i]].push_back(i);
}
for(int i = 0;i < n;i++) sort(doge[i].begin(), doge[i].end()), D[i][1] = inf;
set<pair<int, pair<int, int>>> Q;
D[0][0] = 0;
Q.insert({0, {0, 0}});
while(!Q.empty())
{
pair<int, pair<int, int>> top = *Q.begin();
Q.erase(Q.begin());
//cout << top.second << "\n";
if(top.second.second)
{
for(auto it: doge[top.second.first])
{
if(top.first < D[it][0])
{
if(D[it][0] != inf) Q.erase({D[it][0], {it, 0}});
D[it][0] = top.first;
Q.insert({D[it][0], {it, 0}});
}
}
}
else
{
for(int i = B[top.second.first];i < n;i += P[top.second.first])
{
int c = top.first+(abs(i-B[top.second.first])/P[top.second.first]);
if(c < D[i][1])
{
if(D[i][1] != inf) Q.erase({D[i][1], {i, 1}});
D[i][1] = c;
Q.insert({D[i][1], {i, 1}});
}
if(go(top.second.first, i)) break;
}
for(int i = B[top.second.first];i >= 0;i -= P[top.second.first])
{
int c = top.first+(abs(i-B[top.second.first])/P[top.second.first]);
if(c < D[i][1])
{
if(D[i][1] != inf) Q.erase({D[i][1], {i, 1}});
D[i][1] = c;
Q.insert({D[i][1], {i, 1}});
}
if(go(top.second.first, i)) break;
}
}
}
printf("%d\n", (D[1][0] >= inf)?-1:D[1][0]);
}
