#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<vector<pair<int, int>>> G; // first = destination, second = cost
vector<vector<int>> building;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
G.resize(N);
building.resize(N);
int start, end, p;
cin >> start >> p; building[start].emplace_back(p);
cin >> end >> p; building[end].emplace_back(p);
for (int i = 2; i < M; i++) {
int b, p;
cin >> b >> p;
building[b].emplace_back(p);
}
for (auto &n : building) {
sort(n.begin(), n.end());
n.resize(unique(n.begin(), n.end()) - n.begin());
}
/* Build Graph */
for (int i = 0; i < N; i++) {
for (auto p : building[i]) {
for (int step = 1; i + step * p < N; step++) { // forward
G[i].emplace_back(i + step * p, step);
if (binary_search(building[i + step * p].begin(), building[i + step * p].end(), p)) break;
}
for (int step = 1; i - step * p >= 0; step++) { // backward
G[i].emplace_back(i - step * p, step);
if (binary_search(building[i - step * p].begin(), building[i - step * p].end(), p)) break;
}
}
}
for (auto &n : G) {
sort(n.begin(), n.end());
n.resize(unique(n.begin(), n.end()) - n.begin());
}
/* Dijkstra on created graph */
int ans = INT_MAX;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.emplace(0, start);
vector<int> dist(N, INT_MAX);
dist[start] = 0;
while (!pq.empty()) {
int n = pq.top().second, d = pq.top().first;
pq.pop();
if (dist[n] != d)
continue;
if (n == end) {
ans = d;
break;
}
for (auto v : G[n]) {
if (dist[v.first] == INT_MAX || dist[v.first] > d + v.second) {
dist[v.first] = d + v.second;
pq.emplace(dist[v.first], v.first);
}
}
}
if (ans == INT_MAX)
ans = -1;
cout << ans << "\n";
return 0;
}
