#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int) (x).size())
using namespace std;
const int MAXN = 3e4+100;
int N, M, S, E, B[MAXN], P[MAXN];
vector<int> adj[MAXN];
void read(){
cin >> N >> M;
for(int i = 0; i < M; i++){
cin >> B[i] >> P[i];
adj[B[i]].pb(P[i]);
}
S = B[0], E = B[1];
}
void solve(){
read();
vector<int> dp(N, INT_MAX);
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, S});
dp[S] = 0;
while(!pq.empty()){
int dist = pq.top().ff;
int v = pq.top().ss;
pq.pop();
if(dp[v] < dist){
continue;
}
if(v == E) break;
for(auto p : adj[v]){
for(int u = v + p, w = 1; u < N; u += p, w++){
if(dp[u] > dp[v] + w){
dp[u] = dp[v] + w;
pq.push({dp[u], u});
}
}
for(int u = v - p, w = 1; u >= 0; u -= p, w++){
if(dp[u] > dp[v] + w){
dp[u] = dp[v] + w;
pq.push({dp[u], u});
}
}
}
}
cout << dp[E];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
