#include <bits/stdc++.h>
using namespace std;
#define end __end__
const int can = 350;
int n,m,start,end;
vector <int> power[30009];
int l[30009][can + 3];
struct doges {
int vertice,jump,cost;
bool operator < (const doges & other) const {
return cost > other.cost;
}
};
void djt() {
for (int i = 1;i <= n;i++) for (int j = 1;j <= can + 1;j++) l[i][j] = 1e9;
l[start][can + 1] = 0;
priority_queue <doges> pq;
pq.push({start,can + 1,l[start][can + 1]});
while (pq.size()) {
int pos = pq.top().vertice,jump = pq.top().jump,cost = pq.top().cost;
pq.pop();
if (cost > l[pos][jump]) continue;
if (pos == end) {
cout << l[pos][jump];
exit(0);
}
//TH1: Tiep tuc dung jump
if (jump <= can) {
if (pos - jump >= 1 && l[pos - jump][jump] > cost + 1) {
l[pos - jump][jump] = cost + 1;
pq.push({pos - jump,jump,l[pos - jump][jump]});
}
if (pos + jump <= n && l[pos + jump][jump] > cost + 1) {
l[pos + jump][jump] = cost + 1;
pq.push({pos + jump,jump,l[pos + jump][jump]});
}
}
//TH2: Dung power khac
for (auto pw : power[pos]) {
if (pw > can) {
for (int i = 1;pos - i * pw >= 1;i++) {
if (l[pos - i * pw][can + 1] > cost + i) {
l[pos - i * pw][can + 1] = cost + i;
pq.push({pos - i * pw,can + 1,l[pos - i * pw][can + 1]});
}
}
for (int i = 1;pos + i * pw <= n;i++) {
if (l[pos + i * pw][can + 1] > cost + i) {
l[pos + i * pw][can + 1] = cost + i;
pq.push({pos + i * pw,can + 1,l[pos + i * pw][can + 1]});
}
}
} else {
if (l[pos][pw] > cost) {
l[pos][pw] = cost;
pq.push({pos,pw,l[pos][pw]});
}
}
}
}
cout << -1;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
// freopen(".inp","r",stdin);
// freopen(".out","w",stdout);
cin >> n >> m;
for (int i = 1;i <= m;i++) {
int b,p;cin >> b >> p;
b++;
if (i == 1) start = b;
if (i == 2) end = b;
power[b].push_back(p);
}
djt();
}
/*
Thuong em khi mua thu
Thuong em sang mua ha
Thuong em bang qua mua dong,gui gio xuan om em vao long
Thuong em bao mua mua
Tham thuong luon bao mua nang
Thuong yeu em khong doi thay,gio mat em tim toi hao gay ):
*/
