// 4
// That shouldn't be able to pass subtask 1.
#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;};
std::vector<T> data(numDog);
for(auto& [home, power]: data){
std::cin>>home>>power;
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 Edge{int node, length;};
std::vector<std::vector<Edge>> 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, length=1; next>=0; next-=power,++length){
add[home].push_back({next, length});
if(std::binary_search(begin(lengthsAt[next]), end(lengthsAt[next]), power)) break;
}
for(int next=home+power, length=1; next<numBlock; next+=power,++length){
add[home].push_back({next, length});
if(std::binary_search(begin(lengthsAt[next]), end(lengthsAt[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 [other, edgeLength]: add[node]){
auto nextDistance=curDistance+edgeLength;
if(nextDistance<distance[other]){
queue.push({other, distance[other]=nextDistance});
}
}
}
std::cout<<"-1\n";
}
