#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 = 30010;
const int Sq = 200;
const int INF = 1000000010;
vector<int> pws[Max];
ll dist[Max][Sq + 10];
vector<pair<pii, int> > N[Max][Sq + 10];
void DFS(pii v)
{
//cout << "(" << v.F << "," << v.S << ") = " << dist[v.F][v.S] << "\n";
for(var u : N[v.F][v.S])
if(dist[u.F.F][u.F.S] > dist[v.F][v.S] + u.S)
{
dist[u.F.F][u.F.S] = dist[v.F][v.S] + u.S;
DFS(u.F);
}
}
void connect(pii a , pii b , int d)
{
N[a.F][a.S].pb(mp(b , d));
}
int main()
{
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[i][0] = INF;
for(int j = 1; j <= Sq; j++)
{
dist[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 , x) , mp(i , 0) , 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);
}
}
}
dist[b0][0] = 0;
//DFS(mp(b0 , 0));
cout << dist[b1][0] << '\n';
}
