#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0) ,cin.tie(0),cout.tie(0);
#pragma GCC optimize("O3,unroll-loops")
const int maxn = 2e3+3 , mod = 1e9+7 , inf = 1e15;
int n,m;
int p[maxn];
int b[maxn];
vector <pii> adj[maxn];
int dis[maxn];
priority_queue <pii , vector<pii> , greater<pii>> pq;
int32_t main(){
fast_io
cin >> n >> m;
for(int i = 0 ; i < m ; i++){
dis[i] = inf;
cin >> b[i] >> p[i];
}
for(int i = 0 ; i < m ; i++){
for(int j = i+1 ; j < m ; j++){
if(b[j]%p[i] == b[i]%p[i]) adj[i].pb({j,abs(b[j]-b[i])/p[i]});
if(b[j]%p[j] == b[i]%p[j]) adj[j].pb({i,abs(b[j]-b[i])/p[j]});
}
}
dis[0] = 0;
pq.push({0,0});
while(pq.size()){
auto [d,v] = pq.top();
pq.pop();
if(d > dis[v])continue;
for(auto [u,w] : adj[v]){
if(dis[v]+w < dis[u]){
dis[u] = dis[v]+w;
pq.push({dis[u],u});
}
}
}
cout << dis[1] << endl;
return 0;
}
