#include <bits/stdc++.h>
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
class rep {
struct Iter {
usize itr;
constexpr Iter(const usize pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept { ++itr; }
constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
constexpr usize operator*() const noexcept { return itr; }
};
const Iter first, last;
public:
explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {}
constexpr Iter begin() const noexcept { return first; }
constexpr Iter end() const noexcept { return last; }
};
template <class T, T Div = 2> constexpr T INFTY = std::numeric_limits<T>::max() / Div;
template <class T> bool setmin(T& lhs, const T& rhs) {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
template <class T> using Vec = std::vector<T>;
template <class T> using Heap = std::priority_queue<T, Vec<T>, std::greater<T>>;
void main_() {
usize N, M;
std::cin >> N >> M;
Vec<usize> B(M), P(M);
Vec<Vec<usize>> lives(N);
for (const auto i : rep(0, M)) {
std::cin >> B[i] >> P[i];
lives[B[i]].push_back(i);
}
Vec<std::array<u32, 150>> dist(N);
for (auto& v : dist) {
v.fill(INFTY<u32>);
}
Heap<std::tuple<u32, usize, usize>> heap;
const auto push = [&](const usize u, const usize k, const u32 d) {
if (setmin(dist[u][k], d)) {
heap.emplace(d, u, k);
}
};
push(B[0], 0, 0);
while (!heap.empty()) {
const auto [d, u, k] = heap.top();
heap.pop();
if (dist[u][k] < d) {
continue;
}
if (k != 0) {
push(u, 0, d);
if (u >= k) {
push(u - k, k, d + 1);
}
if (u + k < N) {
push(u + k, k, d + 1);
}
continue;
}
for (const auto x : lives[u]) {
const auto l = P[x];
if (l < 150) {
push(u, l, d);
} else {
usize v = u;
u32 c = d;
while (v >= l) {
v -= l;
c += 1;
push(v, 0, c);
}
v = u;
c = d;
while (v + l < N) {
v += l;
c += 1;
push(v, 0, c);
}
}
}
}
const auto ans = dist[B[1]][0];
if (ans == INFTY<u32>) {
std::cout << -1 << '\n';
} else {
std::cout << ans << '\n';
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
main_();
return 0;
}
