#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int N = 100002;
int vis[N],vv[N];
ll d[N];
pair<int,int> p[N];
vector<pair<int,int> > g[N];
map<int,int> po[N];
int main()
{
int n,m;
cin >> n >> m;
for(int i =0;i<m;i++) {
int a,b;
cin >> a >> b;
p[i] = {a,b};
po[a][b] = i;
}
for(int i =0;i<m;i++) {
int pre=-1;
int x = p[i].f,pr = p[i].s;
if(vis[i]) continue;
for(int j = x%pr;j<n-(n-1-x)%pr;j+=pr) {
int w = abs((j-x)/pr);
if(po[j].count(pr)) {
if(pre == -1) {
pre = j;
continue;
}
w = abs((pre-j)/pr);
g[pre].push_back({j,w});
g[j].push_back({pre,w});
pre = j;
vis[po[j][pr]] = 1;
}
else if(!po[j].empty())g[x].push_back({j,w});
}
vis[i] = 1;
}
for(int i =0;i<n;i++) d[i] = 1e18;
set<pair<ll,ll> > x;
x.insert({0,p[0].f});
while(!x.empty()) {
int v = x.begin()->second;
ll w = x.begin()->first;
x.erase({w,v});
for(auto u : g[v]) {
if(d[u.first] > w + u.second) {
d[u.first] = w + u.second;
x.insert({d[u.first],u.first});
}
}
}
cout << d[p[1].f];
return 0;
}
