/**
* In the name of Allah
* We are nothing and you're everything
* author: najmuddin
**/
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
#define int ll
const char nl = '\n';
const int N = 1e5+5;
const int inf = 1e18+10;
void solve() {
int n, m; cin >> n >> m;
vector<int> b(m), p(m);
vector<tuple<int, int>> g[n];
for (int i = 0; i < m; ++i) {
cin >> b[i] >> p[i];
int k = 1;
while (b[i]-p[i]*k >= 0)g[b[i]].push_back({b[i]-p[i]*k, k}), k++;
k = 1;
while (b[i]+p[i]*k < n)g[b[i]].push_back({b[i]+p[i]*k, k}), k++;
}
vector<int> vis(n+1, inf);
vis[b[0]] = 0;
queue<tuple<int, int>> q;
q.push({b[0], 0});
while (!q.empty()) {
auto [x, a] = q.front();
q.pop();
for (auto [i, w]: g[x]) {
if (vis[i] > w+a)q.push({i, a+w}), vis[i] = a+w;
}
}
if (vis[b[1]] == inf)vis[b[1]] = -1;
cout << vis[b[1]];
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("input.txt", "r", stdin);
int T = 1;
for (int _ = 0; _ < T; ++_) {
solve();
}
return 0;
}
