/*
* Created: 2022-07-23 13:06
*/
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = int;
#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) FOR(i,0,b)
#define FORN(i,a,b) for(int i=int(b)-1;i>=a;i--)
#define per(i,b) FORN(i,0,b)
#define mkp make_pair
#define pb push_back
#define ep emplace_back
#define ff first
#define ss second
#define bg begin()
#define ed end()
#define sz(x) (int)x.size()
#define all(x) (x).bg,(x).ed
#define FIO ios_base::sync_with_stdio(0);\
cin.tie(0);
template<class t> using vc=vector<t>;;
template<class t> using vvc=vc<vc<t>>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi= vc<int>;
using vll= vc<ll>;
#ifdef LOCAL
#include "/home/fuad/cp/dbg.h"
#else
#define dbg(x...)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngll(chrono::steady_clock::now().time_since_epoch().count());
const int inf=1e9;
void solve() {
int n, m;
cin >> n >> m;
map<pll,int> mp;
int b[m], p[m];
vector<int> g[n];
for(int i = 0;i<m;i++) {
cin >> b[i] >> p[i];
if(mp[mkp(b[i], p[i])])continue;
g[b[i]].push_back(p[i]);
}
priority_queue<pll, vc<pll>, greater<pll>> pq;
pq.push(mkp(0, b[0]));
vc<int> dist(n, inf);
dist[b[0]]=0;
vc<bool> vis(n);
while(!pq.empty()) {
int at=pq.top().ss;
pq.pop();
if(vis[at])continue;
vis[at]=1;
for(int i:g[at]) {
int cnt=0;
for(int j = at+i;j<n;j+=i) {
cnt++;
if(dist[j]>dist[at]+cnt) {
dist[j]=dist[at]+cnt;
pq.push(mkp(dist[j], j));
}
}
cnt=0;
for(int j = at-i;j>=0;j-=i) {
cnt++;
if(dist[j]>dist[at]+cnt) {
dist[j]=dist[at]+cnt;
pq.push(mkp(dist[j], j));
}
}
}
}
cout<<dist[b[1]]<<"\n";
}
int main () {
FIO;
int t=1;
// cin >> t;
while(t--)
solve();
}
