#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 +12, MOD = (int)1e9+7;
const int M = 3e4 + 21;
int n,m,b[M],ft[M];
vector<pair<int,int>> x[M],g[N];
void add(int v,int u) {
g[v].push_back({u,1});
g[u].push_back({v,1});
}
int d[N];
void test() {
cin >> n >> m;
for(int i = 0;i < m;i++) {
int p;
cin >> b[i] >> p;
int d = b[i] % p;
x[p].emplace_back(d,i);
}
int it = n - 1;
int num = 0;
for(int i = 1;i < n;i++){
sort(x[i].begin(),x[i].end());
for(int j = 0;j < (int)x[i].size();j++){
if(!j || x[i][j].first != x[i][j - 1].first){
num += (n - x[i][j].first) / i;
}
}
}
if(num > N){
cout << -2;
return;
}
for(int i = 1;i < n;i++){
for(int j = 0;j < (int)x[i].size();j++){
if(!j || x[i][j].first != x[i][j - 1].first){
// cout << i << ' ';
for(int k = x[i][j].first;k < n;k += i){
ft[k] = ++it;
if(k - i >= 0){
add(ft[k - i],ft[k]);
}
g[ft[k]].push_back({k,0});
}
}
int v = b[x[i][j].second];
g[v].push_back({ft[v],0});
}
// cout << '\n';
}
set<pair<int,int>> st;
for(int i = 0;i <= it;i++){
d[i] = 1e9;
}
st.insert({0,b[0]});
d[b[0]] = 0;
while(!st.empty()){
auto [c,v] = (*st.begin());
st.erase(st.begin());
for(auto [to,w]:g[v]){
if(d[to] > d[v] + w){
st.erase({d[to],to});
d[to] = d[v] + w;
st.insert({d[to],to});
}
}
}
if(d[b[1]] == 1e9){
d[b[1]] = -1;
}
cout << d[b[1]];
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int t = 1;
// cin >> t;
while(t--) {
test();
}
}
