#include <bits/stdc++.h> using namespace std; #define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define fi first #define se second #define debug(x) cerr << " - " << #x << ": " << x << endl; #define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl; #define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl; #define sep() cerr << "--------------------" << endl; #define all(x) (x).begin(),(x).end() #define sz(x) (ll)x.size() #define ll long long #define ii pair<int,int> #define v vector<int> #define vii vector<ii> #define vv vector<vector<int> > #define mp make_pair #define INF 1000000000 #define pb push_back #define EPS 1e-9 const int MOD = 1000000007; // 998244353 int B[300005],P[300005]; int dist[300005]; vv vec; int main(){ boost; int N,M; cin>>N>>M; vec.resize(N); for (int i = 0; i < M; ++i){ cin>>B[i]>>P[i]; vec[B[i]].pb(i); dist[i]=INF; } priority_queue<ii> pq; pq.push({0,0}); dist[0]=0; while(!pq.empty()){ ii front=pq.top(); pq.pop(); if(dist[front.se]<front.fi)continue; for (int i = B[front.se],j=0; i < N; i+=P[front.se],j++) { for(auto it:vec[i]){ if(dist[it]>(dist[front.se]+j)){ dist[it]=dist[front.se]+j; pq.push({dist[it],it}); } } } for (int i = B[front.se],j=0; i >= 0; i-=P[front.se],j++) { for(auto it:vec[i]){ if(dist[it]>(dist[front.se]+j)){ dist[it]=dist[front.se]+j; pq.push({dist[it],it}); } } } } cout<<dist[1]<<"\n"; return 0; } //long long //array bounds //special cases //binary search