// 4
// ...
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>
int main(){
std::ios::sync_with_stdio(0);std::cin.tie(0);
int numBlock, numDog; std::cin>>numBlock>>numDog;
std::vector<std::vector<int>> lengthsAt(numBlock);
struct T{
int home, power;
bool operator==(T other) const{return home==other.home and power==other.power;}
};
std::vector<T> data(numDog);
for(auto& [home, power]: data){
std::cin>>home>>power;
}
data.erase(std::remove_if(2+begin(data), end(data), [&](T it){return it==data[0] or it==data[1];}),
data.end());
data.erase(std::unique(begin(data), end(data)), end(data));
numDog=(int)data.size();
for(auto [home, power]: data){
lengthsAt[home].push_back(power);
}
for(auto& it: lengthsAt){
std::sort(begin(it), end(it));
it.erase(std::unique(begin(it), end(it)), end(it));
}
struct EdgeCluster{int first, lastInclusive, power;};
std::vector<std::vector<EdgeCluster>> add(numBlock);
/*
auto const indexBlock=[&](int block){return block;};
auto const indexDog=[&](int dog){return dog+numBlock;};
*/
for(int dog=0; dog<numDog; ++dog){
auto [home, power]=data[dog];
for(int next=home-power; next>=0; next-=power){
if(std::binary_search(begin(lengthsAt[next]), end(lengthsAt[next]), power) or next-power<0){
add[home].push_back({next, home-power, power});
break;
}
}
for(int next=home+power; next<numBlock; next+=power){
if(std::binary_search(begin(lengthsAt[next]), end(lengthsAt[next]), power) or next+power>=numBlock){
add[home].push_back({home+power, next, power});
break;
}
}
}
struct State{int node, distance;
bool operator<(State other) const{return distance>other.distance;}
};
std::vector<int> distance(add.size(), INT_MAX);
std::priority_queue<State> queue;
queue.push({data[0].home, distance[data[0].home]=0});
while(not queue.empty()){
auto [node, curDistance]=queue.top(); queue.pop();
if(curDistance!=distance[node]) continue;
if(node==data[1].home){
std::cout<<curDistance<<'\n';
return 0;
}
for(auto [first, lastInclusive, power]: add[node]){
if(first==node+power){
for(int next=first, length=1; next<=lastInclusive; next+=power,++length){
auto nextDistance=curDistance+length;
if(nextDistance<distance[next]){
queue.push({next, distance[next]=nextDistance});
}
}
}else{
assert(lastInclusive==node-power);
for(int next=lastInclusive, length=1; next>=first; next-=power,++length){
auto nextDistance=curDistance+length;
if(nextDistance<distance[next]){
queue.push({next, distance[next]=nextDistance});
}
}
}
}
}
std::cout<<"-1\n";
}
