#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<int> B(M), P(M);
for(int i = 0; i < M; i++){
cin >> B[i] >> P[i];
}
// Tính SQ = sqrt(N) ngưỡng
int SQ = max(1, (int)(sqrt(N)) );
// pos_at[x] = list các doge tại vị trí x
vector<vector<int>> pos_at(N);
for(int i = 0; i < M; i++){
pos_at[B[i]].push_back(i);
}
// Với các P[u] nhỏ ≤ SQ: ta sẽ lưu trạng thái (position, p)
// dis_small[position][p] = tối thiểu bước để tới position với khả năng nhảy p
// Với P[u] > SQ: ta dùng trạng thái đặc biệt cho mỗi doge
// dis_pos_p: dùng map hoặc vector size N * (SQ+1), large
vector<vector<ll>> dis_small(N, vector<ll>(SQ+1, INF));
// dis_doge for doges with P > SQ: dis_doge[i] = best cost khi gửi tin tới doge i
vector<ll> dis_doge(M, INF);
// priority_queue hoặc deque nếu dùng 0-1 BFS? Nhưng cost nhảy lớn → Dijkstra
using T = pair<ll, pair<int,int>>;
// Pair: (cost, (type, id)), type 0 = small-state (pos,p), type 1 = big-doge (doge index)
// Với type 0: id = pos * (SQ+1) + p, nhưng chúng ta dùng struct
struct State {
ll cost;
int type; // 0 = small, 1 = big doge
int id; // if type=0: encode pos, p; if type=1: doge index
int p_or_unused; // chỉ dùng khi type=0, là p
};
struct Cmp {
bool operator()(State const &a, State const &b) const {
return a.cost > b.cost;
}
};
priority_queue<State, vector<State>, Cmp> pq;
// Khởi đầu: doge 0 có P[0]
if(P[0] <= SQ){
if(dis_small[B[0]][P[0]] > 0){
dis_small[B[0]][P[0]] = 0;
pq.push({0, 0, B[0], P[0]});
}
} else {
if(dis_doge[0] > 0){
dis_doge[0] = 0;
pq.push({0, 1, 0, 0}); // dùng p_or_unused = unused
}
}
// Các boolean để mark truyền tin khi có doge tại cùng position
vector<bool> used_pos_small(N * (SQ+1), false);
vector<bool> used_pos_big(M, false); // để khi doge lớn được xử lý truyền tin
while(!pq.empty()){
State cur = pq.top(); pq.pop();
ll d = cur.cost;
int type = cur.type;
if(type == 1 && cur.id == 1){
// tới doge 1
cout << d << "\n";
return 0;
}
if(type == 0){
int pos = cur.id;
int p = cur.p_or_unused;
if(d > dis_small[pos][p]) continue;
// 1) Nhảy từ (pos, p) tới (pos ± p, p) nếu trong [0,N)
for(int dir : {+1, -1}){
int pos2 = pos + dir * p;
if(pos2 >= 0 && pos2 < N){
ll nd = d + 1;
if(dis_small[pos2][p] > nd){
dis_small[pos2][p] = nd;
pq.push({nd, 0, pos2, p});
}
}
}
// 2) Nếu có doge(s) tại position pos, truyền tin tới các doge nhỏ hoặc lớn
// Man truyền tin = 0 cost, tới doge v tại pos
for(int doge_v : pos_at[pos]){
// v có P[v]
if(P[doge_v] <= SQ){
// chuyển sang trạng thái small (pos, P[v])
if(dis_small[pos][P[doge_v]] > d){
dis_small[pos][P[doge_v]] = d;
pq.push({d, 0, pos, P[doge_v]});
}
} else {
// truyền tin tới big doge
if(dis_doge[doge_v] > d){
dis_doge[doge_v] = d;
pq.push({d, 1, doge_v, 0});
}
}
}
} else { // type == 1: state là “tin được ở doge u, với P[u] lớn”
int u = cur.id;
if(d > dis_doge[u]) continue;
int step = P[u];
int posu = B[u];
// 1) từ doge, nhảy tới các vị trí posu ± k*step
// enumerate cả hai hướng
// mỗi bước mất cost = k
// chúng ta muốn chuyển sang trạng thái small hoặc doge nếu gặp doge
// hướng phải
for(ll x = posu + step, k = 1; x < N; x += step, k++){
ll nd = d + k;
// trạng thái small (x, step) nếu step ≤ SQ; nếu step > SQ, chỉ có thể truyền tin khi gặp doge
if(step <= SQ){
if(dis_small[x][step] > nd){
dis_small[x][step] = nd;
pq.push({nd, 0, (int)x, step});
}
}
// nếu có doge ở x
for(int doge_v : pos_at[x]){
if(dis_doge[doge_v] > nd){
dis_doge[doge_v] = nd;
pq.push({nd, 1, doge_v, 0});
}
}
}
// hướng trái
for(ll x = posu - step, k = 1; x >= 0; x -= step, k++){
ll nd = d + k;
if(step <= SQ){
if(dis_small[x][step] > nd){
dis_small[x][step] = nd;
pq.push({nd, 0, (int)x, step});
}
}
for(int doge_v : pos_at[x]){
if(dis_doge[doge_v] > nd){
dis_doge[doge_v] = nd;
pq.push({nd, 1, doge_v, 0});
}
}
}
}
}
// Nếu không tới doge 1
cout << -1 << "\n";
return 0;
}
