#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
const int INF = 1e9;
const int MAXN = 30005;
const int SQRT = 175; // N ning kvadrat ildizi atrofida
int dist[MAXN][SQRT + 5];
vector<int> doges[MAXN];
int N, M;
struct State {
int b, p, d;
bool operator>(const State& other) const {
return d > other.d;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
int start_b, target_b;
for (int i = 0; i < M; i++) {
int b, p;
cin >> b >> p;
if (i == 0) start_b = b;
if (i == 1) target_b = b;
doges[b].push_back(p);
}
// Masofalarni cheksizlik bilan to'ldirish
for (int i = 0; i < N; i++) {
for (int j = 0; j <= SQRT; j++) dist[i][j] = INF;
}
priority_queue<State, vector<State>, greater<State>> pq;
// Boshlang'ich holat: binoda turganimizda p=0 deb hisoblaymiz
dist[start_b][0] = 0;
pq.push({start_b, 0, 0});
while (!pq.empty()) {
State curr = pq.top();
pq.pop();
int b = curr.b;
int p = curr.p;
int d = curr.d;
if (d > dist[b][p]) continue;
if (b == target_b) {
cout << d << endl;
return 0;
}
// Agar biz binoda bo'lsak (p == 0), shu binodagi barcha dogelarni ishga tushiramiz
if (p == 0) {
for (int np : doges[b]) {
if (np > SQRT) {
// Katta qadamlar uchun oddiy sakrash
for (int i = 1; b + i * np < N; i++) {
if (d + i < dist[b + i * np][0]) {
dist[b + i * np][0] = d + i;
pq.push({b + i * np, 0, d + i});
}
}
for (int i = 1; b - i * np >= 0; i++) {
if (d + i < dist[b - i * np][0]) {
dist[b - i * np][0] = d + i;
pq.push({b - i * np, 0, d + i});
}
}
} else {
// Kichik qadamlar uchun holatga o'tamiz
if (d < dist[b][np]) {
dist[b][np] = d;
pq.push({b, np, d});
}
}
}
} else {
// Kichik qadam p bilan sakrash
// 1. O'ngga
if (b + p < N && d + 1 < dist[b + p][p]) {
dist[b + p][p] = d + 1;
pq.push({b + p, p, d + 1});
}
// 2. Chapga
if (b - p >= 0 && d + 1 < dist[b - p][p]) {
dist[b - p][p] = d + 1;
pq.push({b - p, p, d + 1});
}
// 3. Shu binoda to'xtash (xabarni uzatish)
if (d < dist[b][0]) {
dist[b][0] = d;
pq.push({b, 0, d});
}
}
}
cout << -1 << endl;
return 0;
}
