#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define all(v) v.begin(),v.end()
#define compress(v) v.erase(unique(all(v)),v.end())
using namespace std;
const int INF = (int)1e9;
struct edge {
int v, cost;
bool operator<(const edge& tmp)const {
return cost > tmp.cost;
}
};
int N,M,SQRT;
int B[30000];
vector<int> P[30000];
bool Used[30000][173];
vector<edge> Edge[30000];
int Dist[30000];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
SQRT = (int)sqrt(N);
for (int i = 0; i < M; i++) {
int p;
cin >> B[i] >> p;
if (p < SQRT)
P[B[i]].push_back(p);
else {
for (int j = 1; B[i] - j * p >= 0; j++)
Edge[B[i]].push_back({ B[i] - j * p,j });
for (int j = 1; B[i] + j * p < N; j++)
Edge[B[i]].push_back({ B[i] + j * p,j });
}
}
for (int i = 0; i < N; i++) {
for (int j : P[i]) {
for (int k = 1; i - k * j >= 0; k++) {
Edge[i].push_back({ i - k * j,k });
if (Used[i - k * j][j])
break;
Used[i - k * j][j] = true;
}
}
}
for (int i = N - 1; i >= 0; i--) {
fill(Used[i], Used[i] + SQRT, false);
for (int j : P[i]) {
for (int k = 1; i + k * j < N; k++) {
Edge[i].push_back({ i + k * j,k });
if (Used[i + k * j][j])
break;
Used[i + k * j][j] = true;
}
}
}
priority_queue<edge> q;
fill(Dist, Dist + N, INF);
Dist[B[0]] = 0;
q.push({ B[0],0});
while (!q.empty()) {
auto t = q.top();
q.pop();
if (Dist[t.v] < t.cost)
continue;
for (edge i : Edge[t.v]) {
if (Dist[i.v] > t.cost + i.cost) {
Dist[i.v] = t.cost + i.cost;
q.push({ i.v,Dist[i.v] });
}
}
}
int ans = Dist[B[1]];
if (ans == INF)
ans = -1;
cout << ans;
return 0;
}
