#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(); } }