#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pb push_back
#define int long long
#define fi first
#define se second
const int N = 3e5 + 5, M = 1e9 + 7, LG = 20;
int n , A[N] , dis[N] , m , u , v;
vector<pair<int,int>> lis[N];
void solve(){
cin >> n >> m;
for (int i=0 ; i<n ; i++){
dis[i] = 1e18;
}
for (int i=0 ; i<m ; i++){
cin >> u >> v;
int j=u-v , cn = 1;
while(j >= 0){
lis[u].pb({j,cn});
j -= v;
cn++;
}
j=u+v , cn = 1;
while(j < n){
lis[u].pb({j,cn});
j += v;
cn++;
}
}
int vi[n+1] = {};
priority_queue<pair<int,int>> pq;
dis[0] = 0;
pq.push({0,0});
while(pq.size()){
int v = pq.top().se , sr = -pq.top().fi ; pq.pop();
if (vi[v]) continue;
vi[v] = 1;
dis[v] = sr;
for (auto u : lis[v]){
if (!vi[u.fi]){
pq.push({-(dis[v] + u.se) , u.fi});
}
}
}
cout << dis[1] << endl;
}
signed main(){
// freopen("" , "r" , stdin);
// freopen("" , "w" , stdout);
// cout << setprecision(30);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int ts = 1;
// cin >> ts;
while(ts--){
solve();
}
}
