//
// Created by bg Koh on 2020/10/21.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
int N, M;
vector<vector<int>> jump;
vector<int> discovered;
vector<unordered_map<int,int>> adjList;
int dfs(int startBuild, int jmp, int time, unordered_map<int, int>& soFar, int dir )
{
if (startBuild >= N || startBuild < 0)
return 0;
if (soFar.find(startBuild) != end(soFar)) {
if (soFar[startBuild] > time)
soFar[startBuild] = time;
} else {
soFar.emplace(startBuild, time);
}
dfs(startBuild+((dir == 1) ? jmp:-jmp), jmp, time+1, soFar, dir);
return 1;
}
void makeGraph()
{
for (int i=0; i<N; ++i) {
for (int j : jump[i]) {
unordered_map<int, int> tmp;
dfs(i+j, j, 1, adjList[i], 1); //right
dfs(i-j, j, 1, adjList[i], 0); //left
#if 0
cout << "\n\n" << i << " building:" << endl;
for (auto& k : adjList[i]) {
cout << k.first << ":" << k.second << endl;
}
#endif
}
}
}
int firstDogeLoc = 0, firstJump = 0;
int secondDogeLoc= 0, secondJump = 0;
void input()
{
cin >> N >> M;
jump = vector<vector<int>>(N,vector<int>());
cin >> firstDogeLoc >> firstJump;
jump[firstDogeLoc].emplace_back(firstJump);
cin >> secondDogeLoc >> secondJump;
jump[secondDogeLoc].emplace_back(secondJump);
for (int i=2; i<M; ++i) {
int start, j;
cin >> start >> j;
jump[start].emplace_back(j);
}
adjList = vector<unordered_map<int, int>>(N, unordered_map<int,int>());
}
#define INF (int)2e9
vector<int> shortTime;
int dijkstra()
{
shortTime = vector<int>(N, (int)2e9);
vector<bool> visited(N, false);
shortTime[0] = 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 (distHere == INF)
break;
if (here == secondDogeLoc)
return shortTime[here];
visited[here] = true;
for (auto [there, dist] : adjList[here]) {
int distThere = distHere + dist;
if (!visited[there] && shortTime[there] > distThere) {
shortTime[there] = distThere;
}
}
}
return -1;
//return -1;
}
int main()
{
cout << "Hello world" << endl;
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
freopen("input.txt","r",stdin);
input();
makeGraph();
cout << dijkstra() << endl;
#if 0
unordered_map<int,int> test;
//dfs(2, 2, 1, test, 1);
dfs(4, 2, 1, test, 0);
for (auto& i : test) {
cout << i.first << ":" << i.second << endl;
}
#endif
return 0;
}
