#include <bits/stdc++.h>
using namespace std;
#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 200005
int n,m;
int dizi[lim][2];
vector<pair<int,int>> v[lim];
int vis[lim],dist[lim];
inline void dij(){
for(int i=1;i<=m;i++){
vis[i]=0;
dist[i]=LLONG_MAX;
}
dist[1]=0;
priority_queue<pair<int,int>> pq;
pq.push({0,1});
while(pq.size()){
int node=pq.top().se;
pq.pop();
if(vis[node])continue;
vis[node]=1;
for(auto go:v[node]){
if(dist[node]!=LLONG_MAX && dist[go.fi]>dist[node]+go.se){
dist[go.fi]=dist[node]+go.se;
pq.push({-dist[go.fi],go.fi});
}
}
}
}
int32_t main(){
faster
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>dizi[i][0]>>dizi[i][1];
}
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
if(i==j)continue;
int tut=abs(dizi[i][0]-dizi[j][0]);
if(tut%dizi[i][1])continue;
v[i].pb({j,tut/dizi[i][1]});
}
}
dij();
cout<<dist[2]<<'\n';
return 0;
}
