#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
using ll = long long;
const int inf = 1e9 + 5;
bool chmin(int &a, const int &b) {
return a > b ? a = b, true : false;
}
void solve() {
int n, m; cin >> n >> m;
vector<int> b(m), p(m);
vector mn(n, vector(n, inf));
for(int i = 0; i < m; i++) {
cin >> b[i] >> p[i];
for(int j = 0; j < n; j += p[i]) {
chmin(mn[b[i]][j], j / p[i]);
}
}
vector<int> d(n, inf);
d[b[0]] = 0;
queue<int> q;
q.push(b[0]);
while(!q.empty()) {
int v = q.front();
q.pop();
for(int to = 0; to < n; to++) {
int dist = abs(v - to);
if( chmin(d[to], d[v] + mn[v][dist]) ) {
q.push(to);
}
}
}
int ans = d[b[1]];
if(ans == inf) ans = -1;
cout << ans << nl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
