#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
const int N = 30005;
const ll inf = 1e18;
vector <int> g[N];
vector <ar <ll, 2>> e[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
int strt = -1, end = -1;
for (int i = 0; i < m; i++) {
int b, p;
cin >> b >> p;
if (i == 0)
strt = b;
else if (i == 1)
end = b;
g[b].push_back(p);
}
vector <ll> vis(n, inf);
vis[strt] = 0;
priority_queue <ar <ll, 2>> q;
q.push({0, strt});
while (!q.empty()) {
auto now = q.top(); q.pop();
int x = now[1];
// if (x == end)
// break;
if (now[0] != vis[x])
continue;
for (int p : g[x]) {
int y = x, cnt = 1;
while (y + p < n) {
if (vis[y + p] > vis[x] + cnt) {
vis[y + p] = vis[x] + cnt;
q.push({vis[y + p], y + p});
}
y += p, cnt++;
}
y = x, cnt = 1;
while (y - p >= 0) {
if (vis[y - p] > vis[x] + cnt) {
vis[y - p] = vis[x] + cnt;
q.push({vis[y - p], y - p});
}
y -= p, cnt++;
}
}
}
if (vis[end] == inf)
cout << -1;
else
cout << vis[end];
}
