#include <iostream>
#include<vector>
#include<algorithm>
#include<set>
const int inf = 1e9;
using namespace std;
vector<pair<int,int>> g[2005];
bool done[2005][2005];
set<pair<int, int>> q; //{dist, pos}
vector<int> dist, arr[2005];
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, m, s = -1, t = -1; cin >> n >> m;
dist.assign(n + 1, inf);
for (int i = 0; i < m; ++i) {
int x, y; cin >> x >> y;
if (i == 0) s = x;
if (i == 1) t = x;
arr[x].push_back(y);
}
for (int i = 0; i <= n; ++i)
sort(arr[i].begin(), arr[i].end(), greater<int>());
for(int x = 0; x <= n; ++x)
for (auto y : arr[x]) {
for (int j = x + y, val = 1; j < n; j += y, ++val)
if (!done[x][j])
g[x].push_back({ j, val }), done[x][j] = 1;
for (int j = x - y, val = 1; j >= 0; j -= y, ++val)
if (!done[x][j])
g[x].push_back({ j, val }), done[x][j] = 1;
}
dist[s] = 0;
q.insert({ 0, s });
while (q.size()) {
auto x = *q.begin(); q.erase(q.begin());
if (x.second == t) { cout << x.first; return 0; }
for(auto y: g[x.second])
if (dist[y.first] > (x.first + y.second)) {
if (dist[y.first] < inf) q.erase({ dist[y.first], y.first });
dist[y.first] = (x.first + y.second);
q.insert({ dist[y.first], y.first });
}
}
cout << -1;
}
