#include <iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<math.h>
const int inf = 1e9;
const int maxn = 300005;
const int mod = (int)1e9 + 7;
using namespace std;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m; cin >> n >> m;
vector<pair<int, int>> d;
vector<int> ans(n + 1, inf);
for (int i = 0; i < m; ++i) {
int x, y; cin >> x >> y;
if (i == 1) ans[x] = 0;
d.push_back({ x, y });
}
for (int i = 0; i < m; ++i)
if (!(abs(d[i].first - d[1].first) % d[i].second))
ans[d[i].first] = abs(d[i].first - d[1].first) / d[i].second;
bool c = 1;
for (int j = 0; ((j < n) && c); ++j) {
c = 0;
for (auto x : d) {
for (int i = x.first, val = 0; i >= 0; i -= x.second, ++val)
if (ans[x.first] > (ans[i] + val)) ans[x.first] = ans[i] + val, c = 1;
for (int i = x.first, val = 0; i < n; i += x.second, ++val)
if (ans[x.first] > (ans[i] + val)) ans[x.first] = ans[i] + val, c = 1;
}
}
cout << ((ans[d[0].first] == inf) ? -1 : ans[d[0].first]);
}
