#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
const int BUC = 175;
int b[30001], p[30001], n, m;
int dist[(BUC+1)*30000+10];
struct node
{
int m, n;
node(int M, int N):n(N){if(M>BUC)M=0; m=M;}
node(){m=n=0;}
node(int x):n(b[x])
{
if(p[x] <= BUC) m = p[x];
else m = 0;
}
bool operator<(const node &A) const{return false;}
};
int& d(const node &A){return dist[A.n*(BUC+1)+A.m];}
std::vector<int> blist[30001];
void add(int P, int B, int nd, priority_queue<pair<int, node> > &Q)
{
//printf("##%d %d %d\n", P, B, nd);
if(B<0 || B>=n) return;
node X(P, B);
if(d(X) == -1 || d(X) > nd)
{
d(X)=nd;
Q.push(make_pair(-d(X), X));
}
}
int abs(int x){return x>0?x:-x;}
int main()
{
int i;
scanf("%d%d", &n, &m);
for(i=0; i<m; i++) scanf("%d%d", b+i, p+i);
for(i=0; i<m; i++) blist[b[i]].push_back(p[i]);
priority_queue<pair<int, node> > Q;
Q.push(make_pair(0, node(0)));
memset(dist, -1, sizeof(dist));
d(node(0)) = 0;
//printf("-%d %d %d\n", dist[352], dist[353], dist[354]);
while(!Q.empty())
{
node x = Q.top().second;
if(d(x) != -Q.top().first)
{
Q.pop();
continue;
}
Q.pop();
if(x.n==b[1] && x.m == 0) break;
if(x.m == 0) for(auto pp: blist[x.n])
{
if(pp <= BUC) add(pp, x.n, d(x), Q);
else for(i=x.n%pp; i<n; i+=pp) add(0, i, d(x)+abs(i-x.n)/pp, Q);
}
else
{
add(0, x.n, d(x), Q);
add(x.m, x.n+x.m, d(x)+1, Q);
add(x.m, x.n-x.m, d(x)+1, Q);
}
}
printf("%d\n", d(node(0, b[1])));
return 0;
}
