#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9;
const ll inf = 1e18;
const ll mod = 1e9+7;
const ld eps = 1e-13;
const ld pi = 3.14159265359;
mt19937 _rand(time(NULL));
clock_t z;
const int mxn = 1e5;
int n, m;
ll b[mxn], p[mxn];
ll dist[mxn];
vector<ll> g[mxn];
bool vis[mxn];
void solve(){
cin >> n >> m;
fr(i, 0, m){
cin >> b[i] >> p[i];
g[b[i]].pb(p[i]);
}
fr(i, 0, n) dist[i] = inf;
pq <pair<ll,int> > Q;
Q.push({0, b[0]});
dist[b[0]] = 0;
while(!Q.empty()){
int c = Q.top().nd;
ll w = Q.top().st;
Q.pop();
if(c == b[1]){
cout<<-w<<endl;
return;
}
if(vis[c]) continue;
vis[c] = true;
for(auto u : g[c]){
for(int i = c + u; i < n; i += u){
if(dist[c] + (i-c)/u < dist[i]){
dist[i] = dist[c] + (i-c)/u;
Q.push({-dist[i], i});
}
}
for(int i = c - u; i >=0; i -= u){
if(dist[c] + (c-i)/u < dist[i]){
dist[i] = dist[c] + (c-i)/u;
Q.push({-dist[i], i});
}
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
