#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <set>
using namespace std;
int N, M;
vector<set<int>> jump;
vector<int> discovered;
vector<unordered_map<int,int>> adjList;
int firstDogeLoc = 0, firstJump = 0;
int secondDogeLoc= 0, secondJump = 0;
void input()
{
cin >> N >> M;
jump = vector<set<int>>(N,set<int>());
cin >> firstDogeLoc >> firstJump;
jump[firstDogeLoc].emplace(firstJump);
cin >> secondDogeLoc >> secondJump;
jump[secondDogeLoc].emplace(secondJump);
for (int i=2; i<M; ++i) {
int start, j;
cin >> start >> j;
jump[start].emplace(j);
}
adjList = vector<unordered_map<int, int>>(N, unordered_map<int,int>());
}
#define INF (int)2e9
vector<int> shortTime;
int dijkstra2()
{
shortTime = vector<int>(N, INF);
priority_queue<pair<int, int>> q;
q.emplace(0, firstDogeLoc);
shortTime[firstDogeLoc] = 0;
while (!q.empty()) {
auto [soFarDist, here] = q.top();
soFarDist = -soFarDist;
q.pop();
if (shortTime[here] < soFarDist)
continue;
if (here == secondDogeLoc)
return shortTime[here];
for (int j : jump[here]) {
// goto right
for (int time=1, there=here+j*time; there < N; ++time, there=here+j*time ) {
int destDist = soFarDist + time;
if (shortTime[there] > destDist) {
shortTime[there] = destDist;
q.emplace(-destDist, there);
}
}
//goto left
for (int time=1, there=here-j*time; there >= 0; ++time, there=here-j*time ) {
int destDist = soFarDist + time;
if (shortTime[there] > destDist) {
shortTime[there] = destDist;
q.emplace(-destDist, there);
}
}
}
}
return -1;
}
int dijkstraV2()
{
shortTime = vector<int>(N, (int)2e9);
vector<bool> visited(N, false);
shortTime[firstDogeLoc] = 0;
while (true) {
int here = INF;
int distHere = INF;
for (int i=0; i<N; ++i) {
if (shortTime[i] < distHere && !visited[i]) {
here = i;
distHere = shortTime[i];
}
}
if (here == secondDogeLoc)
return shortTime[here];
if (distHere == INF)
break;
visited[here] = true;
for (auto [there, dist] : adjList[here]) {
int distThere = distHere + dist;
if (!visited[there] && shortTime[there] > distThere) {
shortTime[there] = distThere;
}
}
}
return -1;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
//freopen("input.txt","r",stdin);
input();
cout << dijkstra2() << endl;
return 0;
}
