#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>
const int BLK_SIZE = 269;
int x, d;
int src, dest;
int dist[30005][BLK_SIZE+1];
std::vector<int> dogs_less_than_sqrt[30005];
std::vector<int> dogs_greater_than_sqrt[30005];
int bfs(int src, int dest) {
memset(dist,0x3f,sizeof(dist));
std::priority_queue<std::tuple<int,int,int>, std::vector<std::tuple<int,int,int>>, std::greater<std::tuple<int,int,int>>> q;
q.emplace(0,src,0);
dist[src][0] = 0;
while (!q.empty()) {
auto [c, k, cap] = q.top();
q.pop();
// switch dog (<= sqrt)
if (dist[k][0]>dist[k][cap]) {
dist[k][0] = dist[k][cap];
q.emplace(dist[k][0], k, 0);
}
for (const auto& i : dogs_less_than_sqrt[k]) {
if (dist[k][i]>dist[k][cap]) {
dist[k][i] = dist[k][cap];
q.emplace(dist[k][i], k, i);
}
}
// try to go as far as possible (> sqrt)
for (const auto& i : dogs_greater_than_sqrt[k]) {
for (int j = 1; k+j*i < x; j++) {
if (dist[k+j*i][0]>dist[k][cap]+j) {
dist[k+j*i][0] = dist[k][cap]+j;
q.emplace(dist[k+j*i][0], k+j*i, 0);
}
}
for (int j = 1; k-j*i >= 0; j++) {
if (dist[k-j*i][0]>dist[k][cap]+j) {
dist[k-j*i][0] = dist[k][cap]+j;
q.emplace(dist[k-j*i][0], k-j*i, 0);
}
}
}
// use the current dog (<= sqrt)
if (cap!=0) {
if (k-cap>=0&&dist[k-cap][cap]>dist[k][cap]+1) {
dist[k-cap][cap] = dist[k][cap]+1;
q.emplace(dist[k-cap][cap], k-cap, cap);
}
if (k+cap<x&&dist[k+cap][cap]>dist[k][cap]+1) {
dist[k+cap][cap] = dist[k][cap]+1;
q.emplace(dist[k+cap][cap], k+cap, cap);
}
}
}
int ret = 0x3f3f3f3f;
for (int i = 0; i < BLK_SIZE; i++) {
ret = std::min(ret, dist[dest][i]);
}
return ((ret==0x3f3f3f3f) ? -1 : ret);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> x >> d;
for (int i = 0, a, b; i < d; i++) {
std::cin >> a >> b;
if (i==0) {
src = a;
}
else if (i==1) {
dest = a;
}
if (b<=BLK_SIZE) {
dogs_less_than_sqrt[a].emplace_back(b);
}
else {
dogs_greater_than_sqrt[a].emplace_back(b);
}
}
for (int i = 0; i < x; i++) {
std::sort(dogs_less_than_sqrt[i].begin(), dogs_less_than_sqrt[i].end());
std::sort(dogs_greater_than_sqrt[i].begin(), dogs_greater_than_sqrt[i].end());
dogs_less_than_sqrt[i].erase(std::unique(dogs_less_than_sqrt[i].begin(), dogs_less_than_sqrt[i].end()),
dogs_less_than_sqrt[i].end());
dogs_greater_than_sqrt[i].erase(std::unique(dogs_greater_than_sqrt[i].begin(), dogs_greater_than_sqrt[i].end()),
dogs_greater_than_sqrt[i].end());
}
std::cout << bfs(src,dest) << "\n";
}
