#include <bits/stdc++.h>
#define quan160607 "BoundSeq"
#define fi first
#define se second
#define pii pair<int, int>
#define piii pair<int, pii>
#define pb push_back
using namespace std;
typedef long long ll;
const ll oo = 1e18;
const int inf = 2e9;
const int nmax = 3e4 + 5;
void start()
{
// freopen(quan160607".inp","r",stdin);
// freopen(quan160607".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int n, m;
int b[nmax], a[nmax], p[nmax];
vector<int> v[nmax];
const int block = 100;
int dp[nmax][block + 5];
struct gt
{
int dis, u, p;
};
bool operator > (gt a, gt b)
{
return a.dis > b.dis;
}
priority_queue<gt, vector<gt>, greater<gt>> q;
bool minimize(int &a, int b)
{
if(a > b)
{
a = b;
return true;
} else return false;
}
int cnt;
int ans = inf;
void solve_dij()
{
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= block; j++)
dp[i][j] = inf;
}
dp[b[0]][0] = 0;
q.push({dp[b[0]][0], b[0], 0});
while(!q.empty())
{
gt temp = q.top();
q.pop();
int dis = temp.dis, u = temp.u, pk = temp.p;
if(u == b[1]) ans = min(ans, dp[u][pk]);
if(dis != dp[u][pk])
continue;
dp[u][0] = min(dp[u][0], dp[u][pk]);
if(pk > 0) // true
{
if(u - pk >= 0) {
if(minimize(dp[u - pk][pk], dp[u][pk] + 1))
q.push({dp[u - pk][pk], u - pk, pk});
}
if(u + pk < n) {
if(minimize(dp[u + pk][pk], dp[u][pk] + 1))
q.push({dp[u + pk][pk], u + pk, pk});
}
}
for(auto x : v[u])
{
if(x > block)
{
//dp[u][x]
cnt = 0;
for(int i = u; i < n; i += x) {
if(minimize(dp[i][0], dp[u][0] + cnt)) {
q.push({dp[i][0], i, 0});
}
cnt++;
}
cnt = 0;
for(int i = u; i >= 0; i -= x) {
if(minimize(dp[i][0], dp[u][0] + cnt)) {
q.push({dp[i][0], i, 0});
}
cnt++;
}
}
else {
if(u - x >= 0) {
if(minimize(dp[u - x][x], dp[u][0] + 1))
q.push({dp[u - x][x], u - x, x});
}
if(u + x < n) {
if(minimize(dp[u + x][x], dp[u][0] + 1))
q.push({dp[u + x][x], u + x, x});
}
}
}
}
}
int main()
{
start();
cin >> n >> m;
for(int i = 0; i < m; i++)
{
cin >> b[i] >> p[i];
v[b[i]].push_back(p[i]);
}
solve_dij();
cout << (ans == inf ? -1 : ans);
// cout << "\n";
// cout << dp[2][0] << " " << dp[2][1];
}
