#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define endl "\n"
using namespace std;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
int blk = 200;
vector<int> weights[n];
int init = -1, initp = -1, target = -1;
for(int i = 1; i <= m; ++i) {
int b, p;
cin >> b >> p;
if(i == 1)
init = b, initp = p;
else if(i == 2)
target = b;
// b -> pos
// p -> multiple
weights[b].push_back(p);
}
// doge cmn boleh gerak dr ori node (gaboleh meet di tengah)
// hence cukup dijkstra dengan 1 origin, terus klo intersect lainnya bs langsung dijkstra aja
// tiap node ada theoretically n^2 dijkstra state yg mgkn?
// tp yg high modulo itu sparse, jadi bs simpan manual pakai sorted vector/semacamnya
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
// fi -> dist
// se.fi -> idx
// se.se -> current p
//cout << init << " " << initp << endl;
pq.push(mp(0, mp(init, initp)));
int d[n + 1];
unordered_map<int, bool, custom_hash> vis[n];
bool proc_edge[n];
memset(proc_edge, 0, sizeof(proc_edge));
memset(d, -1, sizeof(d));
while(pq.size()) {
int dist = pq.top().fi, idx = pq.top().se.fi, curp = pq.top().se.se;
pq.pop();
//cout << dist << " " << idx << endl;
if(vis[idx][curp])
continue;
if(d[idx] == -1)
d[idx] = dist;
d[idx] = min(d[idx], dist);
if(!proc_edge[idx]) {
for(auto i : weights[idx]) {
if(!vis[idx].count(i)) {
if(idx - i >= 0 && !vis[idx - i][i])
pq.push(mp(dist + 1, mp(idx - i, i)));
if(idx + i < n && !vis[idx + i][i])
pq.push(mp(dist + 1, mp(idx + i, i)));
}
vis[idx][i];
}
proc_edge[idx] = 1;
}
if(!vis[idx][curp]) {
vis[idx][curp] = 1;
if(idx + curp < n && !vis[idx + curp][curp])
pq.push(mp(dist + 1, mp(idx + curp, curp)));
if(idx - curp >= 0 && !vis[idx - curp][curp])
pq.push(mp(dist + 1, mp(idx - curp, curp)));
}
if(idx == target)
break;
}
cout << d[target] << endl;
// use observation: tiap fox max dipake sekali aja
// buat banyak edge -> not feasible
// buat untuk pair idx modulo tertentu sebuah value init
// nanti dia cari minimum dr kiri dan kanan bs pakai pbds untuk cek insertion
// kalo misal insertion ga worth it -> ga usah insert
// bakal di stop kalo distcur >= distnd + costcur
// make dijkstra algo
// pq dist node
// observation: one doge used at most once? yes
// therefore we can just calculate brute force for each doge usage x distances
// divide into 2 parts, < blk and >= blk
// >= blk -> do every distance (manual dijkstra)
// < blk -> need to find a smart trick to handle, try to iterate through every size
// find modulo kongruen, find moving ke tiap distance minimalnya berapa
// karena moving ke tiap distance cmn dijalanin sekali, otomatis tiap sqrt blok itu butuh tepat n aja?
// WRONG !!!
// only check n-i and n+i? -> yes
// untuk n - i dan n + i observasinya adalah kita tidak perlu cek
// tiap dijkstra pny 2 macam, bs pake yg berapapun???
// although belum tentu minimal???
// nanti tiap node yg dikunjungi (mis kunjungi next) itu tambah aja ke prev atau ke nxt
// buat kasus khususnya dia sendiri klo misal
// yg small itu yg masalah? tiap node bs maintain state yg besar
// harus bagi kasus
// di kiri atau di kanan mau ke kiri atau kanan beda kasus
// kalo misal dari kiri ke kanan terus dianya di kiri, berarti klo mau pake pasti harus dr skrg
// tp klo dari kiri ke kanan terus dianya di kanan, ada 2 pilihan, start sekarang atau nanti
// dijkstranya statenya ada 2
// fi -> node biasa
// se -> last used itu se
// tujuannya -> biar kita coba manual tiap node 1...blk itu harus wajib
// tapi yg lebih dr itu cobanya satu per satu
}
