#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;
const int maxn = 3e4+10;
const int mxsq = 110;
const int maxt = maxn*mxsq;
const int inf = 1e9+7;
int len[maxn];
int pos[maxn];
int dist[maxt];
vector<pii> G[maxt];
inline void add_edge(int a, int b, int w, bool nd)
{
G[a].push_back({w, b});
if(nd)
G[b].push_back({w, a});
}
priority_queue<pii, vector<pii>, greater<pii>> pq;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m; cin >> m >> n;
const int sq = 100;
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);
}
}
fill(dist, dist+maxt, inf);
dist[pos[0]] = 0;
pq.push({0, pos[0]});
while(!pq.empty())
{
int t = pq.top().second;
int d = pq.top().first;
pq.pop();
for(pii e: G[t])
{
int u = e.second;
int w = d+e.first;
if(dist[u] <= w)
continue;
dist[u] = w;
pq.push({dist[u], u});
}
}
int x = dist[pos[1]];
if(x == inf) x = -1;
cout << x << endl;
return 0;
}
