#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#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];
unordered_map<int, BruhInt> dist[N];
struct SearchEntry {
int d, i, j;
bool operator>(const SearchEntry &other) const {
return d > other.d;
}
};
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);
}
priority_queue<SearchEntry, vector<SearchEntry>, greater<SearchEntry>> pq;
pq.push({0, 0, start0});
dist[0][start0] = {0};
while (!pq.empty()) {
auto [d, doge, pos] = pq.top();
pq.pop();
if (d > dist[doge][pos]) continue;
if (doge == 1) {
cout << d;
return 0;
}
for (int newpos : {pos - step_size[doge], pos + step_size[doge]}) {
if (newpos < 0 || newpos >= n) continue;
int &newd = dist[doge][newpos];
if (d + 1 >= newd) continue;
newd = d + 1;
pq.push({d + 1, doge, newpos});
}
for (int newdoge : pos2doge[pos]) {
int &newd = dist[newdoge][pos];
if (d >= newd) continue;
newd = d;
pq.push({d, newdoge, pos});
}
}
cout << -1;
return 0;
}
