#include <algorithm>
#include <iostream>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
const int maxn = 3e4+10;
const int mxsq = 210;
const int sq = 200;
const int maxt = maxn*mxsq;
const ll inf = 1e16;
int len[maxn];
int pos[maxn];
ll dist[maxt];
vector<pli> G[maxt];
inline void add_edge(int a, int b, ll w, bool nd)
{
G[a].push_back({w, b});
if(nd)
G[b].push_back({w, a});
}
inline void dijkstra(int s)
{
set<pli> pq;
fill(dist, dist+maxt, inf);
auto mark = [&](int v, ll d)
{
if(dist[v] <= d) return;
pq.erase({dist[v], v});
dist[v] = d;
pq.insert({dist[v], v});
};
mark(s, 0);
while(!pq.empty())
{
int t = pq.begin()->second;
ll d = pq.begin()->first;
pq.erase(pq.begin());
for(pli e: G[t])
{
int u = e.second;
ll w = e.first;
mark(u, d+w);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m; cin >> m >> n;
for(int p = 1; p < sq; p++)
{
for(int i = 0; i < m; i++)
{
if(i + p < m)
add_edge(p*m+i, p*m+i+p, 1, true);
add_edge(p*m+i, i, 0, false);
}
}
for(int i = 0; i < n; i++)
{
cin >> pos[i] >> len[i];
int b = pos[i];
int p = len[i];
if(p >= sq)
{
for(int j = b%p; j < m; j += p)
{
add_edge(b, j, abs(b-j)/p, false);
}
}
else
{
add_edge(b, p*m+b, 0, false);
}
}
dijkstra(pos[0]);
ll x = dist[pos[1]];
if(x == inf) x = -1;
cout << x << endl;
return 0;
}
