#include "bits/stdc++.h"
using namespace std;
int a, b;
vector<int> z[1000005];
int blocksize;
pair<int, int> mark[30005];
struct node {
int val, pos, type;
bool operator>(const node &other) const {
return val > other.val;
}
};
int base;
inline long long encode(int pos, int type) {
return (long long) pos * base + type;
}
unordered_map<long long, int> dist;
void dijkstra() {
priority_queue<node, vector<node>, greater<node>> q;
long long initKey = encode(mark[0].first, mark[0].second);
dist[initKey] = 0;
q.push({0, mark[0].first, mark[0].second});
// Lambda relax giúp cập nhật trạng thái mới nếu tìm được khoảng cách nhỏ hơn
auto relax = [&](int nd, int newPos, int newType) {
long long key = encode(newPos, newType);
auto it = dist.find(key);
if (it == dist.end() || it->second > nd) {
dist[key] = nd;
q.push({nd, newPos, newType});
}
};
while (!q.empty()) {
node cur = q.top();
q.pop();
int d = cur.val, pos = cur.pos, type = cur.type;
long long curKey = encode(pos, type);
if (dist[curKey] < d) continue;
if (type == 0) {
// Lấy local reference giúp tránh overhead lặp lại truy cập z[pos]
const auto &vec = z[pos];
for (int p : vec) {
int newPos = pos + p;
if (newPos < a)
relax(d + 1, newPos, p);
newPos = pos - p;
if (newPos >= 0)
relax(d + 1, newPos, p);
}
} else {
relax(d, pos, 0);
if (type > blocksize) {
// Sử dụng for-loop thay vì while để có cú pháp gọn hơn
for (int step = 1; pos + step * type < a; step++) {
relax(d + step, pos + step * type, 0);
}
for (int step = 1; pos - step * type >= 0; step++) {
relax(d + step, pos - step * type, 0);
}
} else {
int newPos = pos + type;
if (newPos < a)
relax(d + 1, newPos, type);
newPos = pos - type;
if (newPos >= 0)
relax(d + 1, newPos, type);
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> a >> b;
blocksize = sqrt(a);
base = a + 1;
for (int i = 0; i < b; i++){
int x, y;
cin >> x >> y;
z[x].push_back(y);
mark[i] = {x, y};
}
if (b == 0) {
cout << -1;
return 0;
}
// Tăng kích thước reserve của dist để giảm rehashing
dist.reserve(500000);
dijkstra();
long long finalKey = encode(mark[1].first, 0);
if (dist.find(finalKey) != dist.end())
cout << dist[finalKey];
else
cout << -1;
return 0;
}
