#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=(1e9)+10;
int main(){
ll n, m, i, j;
cin >> n >> m;
vector<ll> p(m), b(m), g(n, -1);
for(i = 0; i < m; i++){
cin >> b[i] >> p[i];
g[b[i]] = i;
}
vector<vector<pair<ll, ll>>> v(n);
for(i = 0; i < m; i++){
for(j = b[i] % p[i]; j < n; j += p[i]){
if(g[j] == -1 || i == j) continue;
v[b[i]].push_back({j, (abs(b[i] - j)) / p[i]});
}
}
vector<ll> dp(n, inf);
set<pair<ll, ll>> s;
dp[b[0]]=0;
s.insert({0, b[0]});
while(!s.empty()){
pair<ll, ll> k1=(*s.begin());
ll a1=k1.first, a2=k1.second;
s.erase(s.begin());
for(auto pa: v[a2]){
ll p1=pa.first, p2=pa.second;
if(dp[p1]>a1+p2){
dp[p1]=a1+p2;
s.insert({dp[p1], p1});
}
}
}
if(dp[b[1]] == inf) cout << -1;
else cout << dp[b[1]];
}
