#include<bits/stdc++.h>
#define pb push_back
#define ins insert
#define F first
#define S second
#define var auto
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int Max = 30002;
const int Sq = 95;
const int INF = 1000000010;
vector<int> pws[Max];
int dist[Max * (Sq + 1)];
bool que[Max * (Sq + 1)];
vector<pair<int, int> > N[Max * (Sq + 1)];
void DFS(int v)
{
/*
set<pair<int,int> > st;
st.ins(mp(0 , v));
dist[v] = 0;
while(st.size())
{
v = st.begin()->S;
st.erase(st.begin());
for(var u : N[v])
{
if(dist[u.F] > dist[v] + u.S)
{
st.erase(mp(dist[u.F] , u.F));
dist[u.F] = dist[v] + u.S;
st.ins(mp(dist[u.F] , u.F));
}
}
}
*/
queue<int> q; q.push(v); dist[v] = 0; que[v] = true;
while(q.size())
{
int v = q.front();
q.pop();
que[v] = false;
for(var u : N[v])
{
if(dist[u.F] > dist[v] + u.S)
{
dist[u.F] = dist[v] + u.S;
if(!que[u.F])
{
q.push(u.F);
que[u.F] = true;
}
}
}
}
}
#define index(a , b) ((a) * (Sq+1) + b)
void connect(pii a , pii b , int d)
{
//cout << "(" << a.F << "," << a.S << ") -> (" << b.F << "," << b.S << ")\n";
//N[a.F][a.S].pb(mp(b , d));
N[index(a.F , a.S)].pb(mp(index(b.F , b.S) , d));
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n , m;cin >> n >> m;
int b0 = -1;
int b1 = -1;
for(int i = 0; i < m ; i++)
{
int b , p;cin >> b >> p;
pws[b].pb(p);
if(i == 0)
b0 = b;
if(i == 1)
b1 = b;
}
for(int i = 0; i < n ; i++)
{
dist[index(i , 0)] = INF;
for(int j = 1; j <= Sq; j++)
{
dist[index(i , j)] = INF;
if(i >= j)
{
connect(mp(i , j) , mp(i - j , j) , 1);
connect(mp(i - j , j) , mp(i , j) , 1);
}
connect(mp(i , j) , mp(i , 0) , 0);
}
sort(pws[i].begin() , pws[i].end());
pws[i].resize(unique(pws[i].begin() , pws[i].end()) - pws[i].begin());
for(int x : pws[i])
{
if(x <= Sq)
connect(mp(i , 0) , mp(i , x) , 0);
else
{
for(int j = i - x , d = 1; j >= 0 ; j -= x , d++)
connect(mp(i , 0) , mp(j , 0) , d);
for(int j = i + x , d = 1; j < n ; j += x , d++)
connect(mp(i , 0) , mp(j , 0) , d);
}
}
}
DFS(index(b0 , 0));
if(dist[index(b1 , 0)] < INF)
cout << dist[index(b1 , 0)] << '\n';
else
cout << -1 << '\n';
}
