#include <bits/stdc++.h>
using namespace std;
struct PairHash {
size_t operator()(const pair<int, int>& p) const {
auto h1 = std::hash<int>()(p.first);
auto h2 = std::hash<int>()(p.second);
return h1 ^ (h2 + 0x9e3779b97f4a7c15ULL + (h1 << 6) + (h1 >> 2));
}
};
int a, b;
vector<int> z[1000005];
int blocksize;
pair<int, int> mark[30005];
struct node {
int val, pos, type;
};
unordered_map<pair<int, int>, int, PairHash> dist;
void dial() {
int maxD = (1e8/a)* a;
vector<vector<node>> buckets(maxD + 1);
buckets[0].push_back({0, mark[0].first, mark[0].second});
dist[{mark[0].first, mark[0].second}] = 0;
for (int d = 0; d <= maxD; d++) {
while (!buckets[d].empty()) {
node cur = buckets[d].back();
buckets[d].pop_back();
if (dist[{cur.pos, cur.type}] < d) continue;
if (cur.type == 0) {
for (auto p : z[cur.pos]) {
int newPos = cur.pos + p;
if (newPos < a) {
pair<int,int> key = {newPos, p};
int nd = d + 1;
if (!dist.count(key) || dist[key] > nd) {
dist[key] = nd;
if (nd <= maxD) {
buckets[nd].push_back({nd, newPos, p});
}
}
}
newPos = cur.pos - p;
if (newPos >= 0) {
pair<int,int> key = {newPos, p};
int nd = d + 1;
if (!dist.count(key) || dist[key] > nd) {
dist[key] = nd;
if (nd <= maxD) {
buckets[nd].push_back({nd, newPos, p});
}
}
}
}
} else {
pair<int,int> key0 = {cur.pos, 0};
if (!dist.count(key0) || dist[key0] > d) {
dist[key0] = d;
buckets[d].push_back({d, cur.pos, 0});
}
if (cur.type > blocksize) {
int step = 1;
while (cur.pos + step * cur.type < a) {
int newPos = cur.pos + step * cur.type;
pair<int,int> key0 = {newPos, 0};
int nd = d + step;
if (!dist.count(key0) || dist[key0] > nd) {
dist[key0] = nd;
if (nd <= maxD) {
buckets[nd].push_back({nd, newPos, 0});
}
}
step++;
}
step = 1;
while (cur.pos - step * cur.type >= 0) {
int newPos = cur.pos - step * cur.type;
pair<int,int> key0 = {newPos, 0};
int nd = d + step;
if (!dist.count(key0) || dist[key0] > nd) {
dist[key0] = nd;
if (nd <= maxD) {
buckets[nd].push_back({nd, newPos, 0});
}
}
step++;
}
} else {
int newPos = cur.pos + cur.type;
if (newPos < a) {
pair<int,int> key = {newPos, cur.type};
int nd = d + 1;
if (!dist.count(key) || dist[key] > nd) {
dist[key] = nd;
if (nd <= maxD) {
buckets[nd].push_back({nd, newPos, cur.type});
}
}
}
newPos = cur.pos - cur.type;
if (newPos >= 0) {
pair<int,int> key = {newPos, cur.type};
int nd = d + 1;
if (!dist.count(key) || dist[key] > nd) {
dist[key] = nd;
if (nd <= maxD) {
buckets[nd].push_back({nd, newPos, cur.type});
}
}
}
}
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> a >> b;
blocksize = sqrt(a);
for (int i = 0; i < b; i++){
int x, y;
cin >> x >> y;
z[x].push_back(y);
mark[i] = {x, y};
}
if(b == 0){
cout << -1;
return 0;
}
dist.reserve(100000);
dial();
pair<int,int> finalKey = {mark[1].first, 0};
if(dist.count(finalKey)){
cout << dist[finalKey];
} else {
cout << -1;
}
return 0;
}
