#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm>
using namespace std;
struct BruhInt {
int value = 1e9;
operator int &() { return value; }
};
constexpr int N = 3e4 + 5;
int step_size[N];
vector<int> pos2doge[N];
bool visitedpos[N];
bool visiteddoge[N];
unordered_set<int> visited[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("input.txt", "r", stdin);
int n, m;
cin >> n >> m;
int start0;
for (int doge = 0; doge < m; doge++) {
int start, step;
cin >> start >> step;
if (doge == 0) start0 = start;
step_size[doge] = step;
pos2doge[start].push_back(doge);
}
deque<tuple<int, int, int>> q;
q.emplace_back(0, 0, start0);
visited[0].insert(start0);
visiteddoge[0] = true;
while (!q.empty()) {
auto [d, doge, pos] = q.front();
q.pop_front();
if (doge == 1) {
cout << d;
return 0;
}
if (!visitedpos[pos]) {
visitedpos[pos] = true;
for (int doge : pos2doge[pos]) {
if (visiteddoge[doge]) continue;
q.emplace_front(d, doge, pos);
}
}
for (int newpos : {pos - step_size[doge], pos + step_size[doge]}) {
if (newpos < 0 || newpos >= n) continue;
if (visited[doge].contains(newpos)) continue;
visited[doge].insert(newpos);
q.emplace_back(d + 1, doge, newpos);
}
}
cout << -1;
return 0;
}
