/*input
5 3
0 2
1 1
4 1
*/
#include<bits/stdc++.h>
using namespace std;
const int N=3e5 + 100;
const int mod=1e9 + 7;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl
//Trace prints the name of the variable and the value.
set<int> doges[N];
int src, tar, dist[N];
priority_queue< pii, vector< pii >, greater<pii> > pq;
set<int> visited[N];
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n, m;cin>>n>>m;
for(int i=0;i<n;i++) dist[i]=inf;
for(int i=0;i<m;i++)
{
int b, p;cin>>b>>p;
if(i==0) src=b;
if(i==1) tar=b;
doges[b].insert(p);
}
pq.push(mp(0, src));dist[src]=0;
while(!pq.empty())
{
pii cur=pq.top();pq.pop();
if(cur.f>dist[cur.s]) continue;
for(auto i:doges[cur.s])
{
int moves=0;
for(int j=cur.s+i;j<n;j+=i)
{
moves++;
if(dist[j]>cur.f + moves)
{
dist[j]=cur.f + moves;pq.push(mp(dist[j], j));visited[j].insert(i);
}
else if(visited[j].count(i)!=0) break;
}
moves=0;
for(int j=cur.s-i;j>=0;j-=i)
{
moves++;
if(dist[j]>cur.f + moves)
{
dist[j]=cur.f + moves;pq.push(mp(dist[j], j));visited[j].insert(i);
}
else if(visited[j].count(i)!=0) break;
}
}
}
cout<<dist[tar];
}
