#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define mk make_pair
#define pii pair<int, int>
#define F first
#define S second
#define sz size()
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
const int N = 3e4 + 5;
int b[N], p[N], d[N];
set <pii> st;
int n;
void dij ()
{
int v = st.begin () -> S;
st.erase (st.begin ());
for (int i = 0; i < n; i++)
if (b[v] % p[v] == b[i] % p[v] && d[v] + abs (b[v] - b[i]) / p[v] < d[i])
{
st.erase (mk (d[i], i));
d[i] = d[v] + abs (b[v] - b[i]) / p[v];
st.insert (mk (d[i], i));
}
if (st.sz)
dij ();
}
void Solve ()
{
int m;
cin >> m >> n;
for (int i = 0; i < n; i++)
cin >> b[i] >> p[i];
memset (d, 63, sizeof d);
d[0] = 0;
st.insert (mk (d[0], 0));
dij ();
if (d[1] == d[N - 1])
cout << -1 << endl;
else
cout << d[1] << endl;
}
int32_t main ()
{
ios::sync_with_stdio (0), cin.tie (0), cout.tie (0);
int tt = 1;
// cin >> tt;
while (tt--)
Solve ();
}
