#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
using namespace std;
const int mxN = 3e4 + 5;
const int inf = 1e9;
struct pair_hash {
template <class T1, class T2>
std::size_t operator() (const std::pair<T1, T2>& pair) const {
auto hash1 = std::hash<T1>{}(pair.first);
auto hash2 = std::hash<T2>{}(pair.second);
return hash1 ^ (hash2 << 1);
}
};
vector<int> pos[mxN];
int n, m, x, y;
unordered_map<int, int> dp[mxN];
signed main(){
ios::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
vector<int> d(m), s(m);
for(int i = 0; i < m; ++i){
cin >> d[i] >> s[i];
if(i == 0) x = d[i], y = s[i];
pos[d[i]].push_back(s[i]);
}
priority_queue<tuple<int, int, int>> pq;
pq.push({0, x, y});
dp[x][y] = 0;
int ans = inf;
while(pq.size()){
auto [dist, id, mov] = pq.top();
pq.pop();
dist = -dist;
if(id == d[1]){
ans = min(ans, dist);
continue;
}
if(dp[id][mov] < dist) continue;
for(auto it : pos[id]){
if((id + it) <= (n - 1) && (!dp[id + it].count(it) || dp[id + it][it] > (dist + 1))){
dp[id + it][it] = dist + 1;
pq.push({-dp[id + it][it], id + it, it});
}
if((id - it) >= 0 && (!dp[id - it].count(it) || dp[id - it][it] > (dist + 1))){
dp[id - it][it] = dist + 1;
pq.push({-dp[id - it][it], id - it, it});
}
}
if((id + mov) <= (n - 1) && (!dp[id + mov].count(mov) || dp[id + mov][mov] > (dist + 1))){
dp[id + mov][mov] = dist + 1;
pq.push({-dp[id + mov][mov], id + mov, mov});
}
if((id - mov) >= 0 && (!dp[id - mov].count(mov) || dp[id - mov][mov] > (dist + 1))){
dp[id - mov][mov] = dist + 1;
pq.push({-dp[id - mov][mov], id - mov, mov});
}
}
if(ans == inf) cout << -1 << "\n";
else cout << ans << "\n";
return 0;
}
