#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double
const ll N = 5e5;
const ll INF = 4e18;
const ll MOD = 1e9 + 7;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc = 1;
// cin >> tc;
for(;tc--;){
ll n, m; cin >> n >> m;
vector<ll> b(m + 5), p(m + 5);
for(int i = 1; i <= m; i++) cin >> b[i] >> p[i];
vector<pii> adj[n + 5];
for(int i = 1; i <= m; i++){
ll cur = 0;
for(int j = b[i] + p[i]; j <= n; j += p[i]){
adj[b[i]].push_back({j, ++cur});
}
cur = 0;
for(int j = b[i] - p[i]; j >= 1; j -= p[i]){
adj[b[i]].push_back({j, ++cur});
}
}
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<ll> dp(n + 5, INF);
dp[0] = 0;
pq.push({dp[0], 0});
for(;!pq.empty();){
auto [dist, idx] = pq.top(); pq.pop();
if(dist > dp[idx]) continue;
for(auto [i, j] : adj[idx]){
if(dp[i] > dist + j){
dp[i] = dist + j;
pq.push({dp[i], i});
}
}
}
cout << dp[1] << "\n";
}
}
/*
*/
